Untitled
unknown
c_cpp
7 months ago
2.1 kB
4
Indexable
Never
#include <stdio.h> #include <stdlib.h> #include <string.h> #define int long long const int 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], graph_len[MAXN], ttl[MAXN], child_done[MAXN]; void get_child(int now) { node *i = graph[now]; while (i) { get_child(i->val); child[now] += child[i->val]; i = i->nxt; } 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 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; } int head = 0, tail = 0; for (int i = 1; i <= n; i++) if (child[i] == 1) queue[tail++] = i; memset(child_done, 0, sizeof(child_done)); memset(ttl, 0, sizeof(ttl)); int ans = 0; while (head != tail) { int i = queue[head++]; int miP = 1e9; for (pair *p = price[i]; p; p = p->nxt) { if (p->end >= t) 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); } }