제출 #906735

#제출 시각아이디문제언어결과실행 시간메모리
906735typ_ik동기화 (JOI13_synchronization)C++17
0 / 100
8063 ms262144 KiB
#include <bits/stdc++.h> #define ll long long #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define watch(x) cout << (#x) << " : " << x << '\n' #define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) using namespace std; const int N = 3e5 + 128; const int LOG = 20; vector <int> g[N]; pair <int, int> edges[N]; int n, m, q; int lift[N][LOG], depth[N], tin[N], tout[N]; int timer = 0; int t[N], ans[N]; int sum(int r) { int ans = 0; for (; r >= 0; r = (r & (r + 1)) - 1) ans += t[r]; return ans; } void add(int idx, int val) { for (; idx < n; idx = idx | (idx + 1)) t[idx] += val; } void dfs(int v, int p = 1) { if (v != 1) depth[v] = depth[p] + 1; lift[v][0] = p; for (int b = 1; b < LOG; b++) lift[v][b] = lift[lift[v][b-1]][b-1]; tin[v] = timer++; for (auto& to : g[v]) if (to != p) dfs(to, v); tout[v] = timer - 1; } int lca(int u, int v) { if (depth[v] > depth[u]) swap(u, v); int k = depth[u] - depth[v]; for (int b = 0; b < LOG; b++) if ((k >> b) & 1) u = lift[u][b]; if (u == v) return u; for (int b = LOG - 1; b >= 0; b--) if (lift[v][b] != lift[u][b]) v = lift[v][b], u = lift[u][b]; return lift[u][0]; } int get(int x) { return sum(tin[x]); } int get(int u, int v) { return get(u) + get(v) - 2 * get(lca(u, v)); } int find_parent(int v) { for (int b = LOG - 1; b >= 0; b--) if (get(lift[v][b], v) == (1 << b)) v = lift[v][b]; return v; } int update(int v, int val) { add(tin[v], val); add(tout[v] + 1, -val); } bool state[N]; int prev_time[N]; void solve() { cin >> n >> m >> q; for (int i = 1; i < n; i++) { cin >> edges[i].first >> edges[i].second; g[edges[i].first].push_back(edges[i].second); g[edges[i].second].push_back(edges[i].first); } for (int i = 1; i <= n; i++) ans[i] = 1; dfs(1); for (int i = 0; i < m; i++) { int idx; cin >> idx; int u = edges[idx].first, v = edges[idx].second; if (depth[u] > depth[v]) swap(u, v); if (state[idx]) { prev_time[idx] = ans[find_parent(u)]; update(v, -1); ans[find_parent(u)] = prev_time[idx]; ans[find_parent(v)] = prev_time[idx]; } else { int res = ans[find_parent(u)] + ans[find_parent(v)] - prev_time[idx]; update(v, 1); ans[find_parent(u)] = res; } state[idx] = !state[idx]; } for (int i = 0; i < q; i++) { int x; cin >> x; cout << ans[find_parent(x)] << '\n'; } } main() { boost; solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

synchronization.cpp: In function 'int update(int, int)':
synchronization.cpp:80:1: warning: no return statement in function returning non-void [-Wreturn-type]
   80 | }
      | ^
synchronization.cpp: At global scope:
synchronization.cpp:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  127 | main() {
      | ^~~~
#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...