Untitled
unknown
c_cpp
a year ago
2.2 kB
2
Indexable
Never
#include <stdio.h> #include <stdlib.h> #include <string.h> #define int long long #define MAXN 1000005 typedef struct pair pair; struct pair { int pri, end; pair *nxt; }; typedef struct node node; struct node { int val; node *nxt; }; pair *price[MAXN]; node *graph[MAXN]; int inv[MAXN], child[MAXN], queue[MAXN], Q[MAXN], graph_len[MAXN], ttl[MAXN], child_done[MAXN],Tail; void get_child(int now) { for(node *i=graph[now];i;i=i->nxt){ get_child(i->val); child[now] += child[i->val]; } child[now]++; } int min(int a, int b) { if (a < b) return a; else return b; } int max(int a, int b) { if (a > b) return a; else return b; } signed main() { int n, m, C; scanf("%lld %lld %lld", &n, &m, &C); for (int i = 2; i <= n; i++) { int x; scanf("%lld", &x); inv[i] = x; node *newNode = malloc(sizeof(node)); newNode->val = i; newNode->nxt = graph[x]; graph[x] = newNode; graph_len[x]++; } get_child(1); for (int i = 1; i <= n; i++) if (child[i] == 1) Q[Tail++] = i; for (int t = 0; t < m; t++) { for (int i = 1; i <= n; i++) { pair *newNode = malloc(sizeof(pair)); scanf("%lld %lld", &newNode->pri, &newNode->end); newNode->end += t; newNode->nxt = price[i]; price[i] = newNode; child_done[i] = ttl[i] = 0; } int head = 0, tail = 0; for (int i = 0; i < Tail; i++) queue[tail++] = Q[i]; int ans = 0; while (head != tail) { int i = queue[head++]; pair *p = price[i]; int miP = p->pri; while(p->nxt){ if(p->nxt->end < t) p->nxt=p->nxt->nxt; else{ p=p->nxt; miP=min(miP,p->pri); } } ttl[i] += miP; if (ttl[i] <= C) ans = max(ans, child[i]); ttl[inv[i]] += ttl[i]; if (++child_done[inv[i]] == graph_len[inv[i]] && ttl[inv[i]] <= C) queue[tail++] = inv[i]; } printf("%lld\n", ans); } }