Submission #666775

#TimeUsernameProblemLanguageResultExecution timeMemory
666775rainboyWorst Reporter 4 (JOI21_worst_reporter4)C11
100 / 100
339 ms87276 KiB
#include <stdio.h> #include <stdlib.h> #define N 200000 #define LN 18 /* LN = ceil(log2(N)) */ #define N_ (N * (LN + 1) + 1) long long max(long long a, long long b) { return a > b ? a : b; } unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } int aa[N], cc[N], n; void sort(int *ii, int l, int r) { while (l < r) { int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp; while (j < k) if (aa[ii[j]] == aa[i_]) j++; else if (aa[ii[j]] < aa[i_]) { tmp = ii[i], ii[i] = ii[j], ii[j] = tmp; i++, j++; } else { k--; tmp = ii[j], ii[j] = ii[k], ii[k] = tmp; } sort(ii, l, i); l = k; } } int *ej[N], eo[N]; void append(int i, int j) { int o = eo[i]++; if (o >= 2 && (o & o - 1) == 0) ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]); ej[i][o] = j; } int ll[N_], rr[N_], _; long long xx[N_]; int add(int t, int l, int r, int i, int x) { int t_ = t ? t : ++_, m; xx[t_] += x; if (r - l > 1) { m = (l + r) / 2; if (i < m) ll[t_] = add(ll[t_], l, m, i, x); else rr[t_] = add(rr[t_], m, r, i, x); } return t_; } int x; int remove_(int t, int l, int r, int i) { int m; if (l >= i || x == 0 || !t) return t; if (r <= i && x >= xx[t]) { x -= xx[t]; return 0; } if (r - l == 1) { xx[t] -= x, x = 0; return t; } m = (l + r) / 2; rr[t] = remove_(rr[t], m, r, i), ll[t] = remove_(ll[t], l, m, i); xx[t] = xx[ll[t]] + xx[rr[t]]; return ll[t] || rr[t] ? t : 0; } long long query(int t, int l, int r, int i) { int m; if (r <= i || !t) return 0; if (l >= i) return xx[t]; m = (l + r) / 2; return query(ll[t], l, m, i) + query(rr[t], m, r, i); } int merge(int t1, int t2, int l, int r) { int m; if (!t1) return t2; else if (!t2) return t1; xx[t1] += xx[t2]; if (r - l > 1) { m = (l + r) / 2; ll[t1] = merge(ll[t1], ll[t2], l, m), rr[t1] = merge(rr[t1], rr[t2], m, r); } return t1; } char visited[N]; int tt[N]; void dfs(int p, int i) { int o; if (p != -1) visited[i] = 1; tt[i] = 0; for (o = eo[i]; o--; ) { int j = ej[i][o]; if (j != p && visited[j] != -1) { dfs(i, j); tt[i] = merge(tt[i], tt[j], 0, n); } } if (p != -1) x = cc[i], tt[i] = add(remove_(tt[i], 0, n, aa[i]), 0, n, aa[i], cc[i]); } int main() { static int pp[N], ii[N]; static long long cc_[N]; int i, j, k, a, t; long long ans, x; scanf("%d", &n); for (i = 0; i < n; i++) ej[i] = (int *) malloc(2 * sizeof *ej[i]); ans = 0; for (i = 0; i < n; i++) { scanf("%d%d%d", &pp[i], &aa[i], &cc[i]), pp[i]--; ans += cc[i]; append(pp[i], i); } for (i = 0; i < n; i++) ii[i] = i; sort(ii, 0, n); for (i = 0, a = 0; i < n; i++) aa[ii[i]] = i + 1 == n || aa[ii[i + 1]] != aa[ii[i]] ? a++ : a; for (i = 0; i < n; i++) if (!visited[i]) { j = i; while (!visited[j]) visited[j] = 1, j = pp[j]; k = j; do visited[k] = -1, k = pp[k]; while (k != j); t = 0; do { dfs(-1, k); t = merge(t, tt[k], 0, n); cc_[aa[k]] += cc[k]; k = pp[k]; } while (k != j); x = xx[t]; do { a = aa[k]; if (cc_[a] != 0) x = max(x, query(t, 0, n, a) + cc_[a]), cc_[a] = 0; k = pp[k]; } while (k != j); ans -= x; } printf("%lld\n", ans); return 0; }

Compilation message (stderr)

worst_reporter2.c: In function 'append':
worst_reporter2.c:42:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   42 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
worst_reporter2.c: In function 'main':
worst_reporter2.c:136:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
worst_reporter2.c:141:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   scanf("%d%d%d", &pp[i], &aa[i], &cc[i]), pp[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...