Submission #116227

#TimeUsernameProblemLanguageResultExecution timeMemory
116227Just_Solve_The_ProblemSynchronization (JOI13_synchronization)C++11
100 / 100
326 ms21236 KiB
#include <bits/stdc++.h> using namespace std; const int N = (int)2e5 + 7; vector<int> gr[N]; vector<pair<int, int>> ed; int n, m, q; int tin[N], tout[N], pos[N]; int st[N]; int tiktak; int tree[N * 4], ans[N], lst[N]; void dfs(int v, int pr) { tin[v] = ++tiktak; pos[tiktak] = v; for (int id : gr[v]) { int to = ed[id].first + ed[id].second - v; if (to == pr) continue; dfs(to, v); } tout[v] = ++tiktak; } void build(int v, int l, int r) { if (l == r) { tree[v] = tout[pos[l]]; return ; } int mid = (l + r) >> 1; build(v + v, l, mid); build(v + v + 1, mid + 1, r); tree[v] = max(tree[v + v], tree[v + v + 1]); } void upd(int pos, int val, int v = 1, int tl = 1, int tr = n + n) { if (tl == tr) { tree[v] = val; return ; } int mid = (tl + tr) >> 1; if (pos <= mid) { upd(pos, val, v + v, tl, mid); } else { upd(pos, val, v + v + 1, mid + 1, tr); } tree[v] = max(tree[v + v], tree[v + v + 1]); } int find(int l, int r, int lim, int v = 1, int tl = 1, int tr = n + n) { if (tl > r || tr < l || tree[v] <= lim) return -1; if (tl == tr) return tl; int mid = (tl + tr) >> 1; int res = find(l, r, lim, v + v + 1, mid + 1, tr); if (res == -1) res = find(l, r, lim, v + v, tl, mid); return res; } int get(int l, int r, int v = 1, int tl = 1, int tr = n + n) { if (tl > r || tr < l) return -1; if (l <= tl && tr <= r) return tree[v]; int mid = (tl + tr) >> 1; return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr)); } int findroot(int u) { int res = find(1, tin[u], tin[u]); return (res == -1) ? 1 : pos[res]; } main() { scanf("%d %d %d", &n, &m, &q); for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); gr[u].push_back(ed.size()); gr[v].push_back(ed.size()); ed.push_back({u, v}); } dfs(1, 1); for (int i = 1; i <= n; i++) { ans[i] = 1; } for (int i = 0; i < n - 1; i++) { if (tin[ed[i].first] > tin[ed[i].second]) swap(ed[i].first, ed[i].second); } build(1, 1, n + n); for (int i = 1; i <= m; i++) { int id; scanf("%d", &id); id--; int u = findroot(ed[id].first); int v = ed[id].second; if (!st[id]) { ans[u] += ans[v] - lst[v]; upd(tin[v], tin[v]); } else { ans[v] = lst[v] = ans[u]; upd(tin[v], tout[v]); } st[id] ^= 1; //cout << find(1, tin[ed[id].first], tin[ed[id].first]) << ' ' << ed[id].first << ' ' << u << endl; //cout << "ZASDSDA " << get(2, 2) << endl; } for (int i = 1; i <= n; i++) { ans[i] = ans[findroot(i)]; } for (int i = 1, x; i <= q; i++) { scanf("%d", &x); printf("%d\n", ans[x]); } }

Compilation message (stderr)

synchronization.cpp:73:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &id); id--;
   ~~~~~^~~~~~~~~~~
synchronization.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
#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...