Submission #1072292

#TimeUsernameProblemLanguageResultExecution timeMemory
1072292rainboySummer Driving (CCO24_day1problem3)C11
1 / 25
6067 ms54356 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 300000 #define INF 0x3f3f3f3f int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } int n, r, a, b; 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 ii[N], dd[N], pp[N], pp_[N], ll[N], ta[N], tb[N], qu[N]; void dfs1(int i) { static int t_; static int stack[N]; int o; qu[ta[i] = t_++] = i; stack[dd[i]] = i; pp_[i] = dd[i] < a - 1 ? -1 : stack[dd[i] - a + 1]; ll[i] = 0; for (o = eo[i]; o--; ) { int j = ej[i][o]; if (j != pp[i]) { dfs1(j); ll[i] = max(ll[i], ll[j] + 1); } } tb[i] = t_; } char dp[N], dq[N]; void mark(int l, int r, int d) { int i, a; for (a = l; a <= r; a++) { i = qu[a]; if (dd[i] <= d && dq[i]) dq[i] = 0; } } int solve(int k) { static char dq_[N]; static int dd1[N], dd2[N]; int h, h_, i, j, j_, j1, j2, o, bad; for (h = n - 1; h >= 0; h--) { i = ii[h]; dd1[i] = i < k ? 0 : INF; for (o = eo[i]; o--; ) { j = ej[i][o]; if (j != pp[i]) dd1[i] = min(dd1[i], dd1[j] + 1); } } memset(dq, 1, n * sizeof *dq), memset(dq_, 0, n * sizeof *dq_); for (h = n - 1, h_ = n - 1; h >= 0; h--) { i = ii[h]; while (h_ >= 0 && dd[j = ii[h_]] - dd[i] >= a) { if (dq[j]) dq_[pp_[j]] = 1; h_--; } if (ll[i] < a) { if (dd1[i] > b) dp[i] = 1; else { dp[i] = 0; j_ = i >= k ? -1 : -2; for (o = eo[i]; o--; ) { j = ej[i][o]; if (j != pp[i] && dd1[j] < b) j_ = j_ == -1 ? j : -2; } if (j_ == -2) mark(ta[i], tb[i] - 1, dd[i] + b); else if (j_ != -1) mark(ta[i], ta[j_] - 1, dd[i] + b), mark(tb[j_], tb[i] - 1, dd[i] + b); } } else { j_ = -1; for (o = eo[i]; o--; ) { j = ej[i][o]; if (j != pp[i] && dq_[j]) j_ = j_ == -1 ? j : -2; } if (j_ != -1) dp[i] = 1; else { dp[i] = 0; j_ = -2; for (o = eo[i]; o--; ) { j = ej[i][o]; if (j != pp[i] && ll[j] >= a - 1) { j_ = j; break; } } if (j_ == -2) mark(ta[i], tb[i] - 1, dd[i] + b); else mark(ta[i], ta[j_] - 1, dd[i] + b), mark(tb[j_], tb[i] - 1, dd[i] + b); } if (j_ != -2) { bad = i < k; for (o = eo[i]; o--; ) { j = ej[i][o]; if (j != pp[i] && j != j_ && (ll[j] >= a - 1 || dd1[j] < b)) { bad = 1; break; } } if (bad) mark(ta[j_], tb[j_] - 1, dd[i] + b); } } j1 = j2 = -1; for (o = eo[i]; o--; ) { j = ej[i][o]; if (j != pp[i]) { if (j1 == -1 || dd2[j1] > dd2[j]) j2 = j1, j1 = j; else if (j2 == -1 || dd2[j2] > dd2[j]) j2 = j; } } dd2[i] = !dp[i] ? 0 : (j1 == -1 || dd2[j1] == INF ? INF : dd2[j1] + 1); for (o = eo[i]; o--; ) { j = ej[i][o], j_ = j != j1 ? j1 : j2; if (j_ != -1) mark(ta[j], tb[j] - 1, dd[i] + b - (dd2[j_] + 1)); } } return dp[r]; } int main() { int cnt, h, i, j, o, k, lower, upper; scanf("%d%d%d%d", &n, &r, &a, &b), r--; if (a <= b) { printf("1\n"); return 0; } for (i = 0; i < n; i++) ej[i] = (int *) malloc(2 * sizeof *ej[i]); for (h = 0; h < n - 1; h++) { scanf("%d%d", &i, &j), i--, j--; append(i, j), append(j, i); } cnt = 0; dd[r] = 0, pp[r] = -1, ii[cnt++] = r; for (h = 0; h < cnt; h++) { i = ii[h]; for (o = 0; o < eo[i]; o++) { j = ej[i][o]; if (j != pp[i]) dd[j] = dd[i] + 1, pp[j] = i, ii[cnt++] = j; } } dfs1(r); lower = 0, upper = n; while (upper - lower > 1) { k = (lower + upper) / 2; if (solve(k)) lower = k; else upper = k; } printf("%d\n", upper); return 0; }

Compilation message (stderr)

Main.c: In function 'append':
Main.c:17:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:154:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |  scanf("%d%d%d%d", &n, &r, &a, &b), r--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:162:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...