Submission #873430

#TimeUsernameProblemLanguageResultExecution timeMemory
873430AMnuSynchronization (JOI13_synchronization)C++17
30 / 100
349 ms152356 KiB
# include <bits/stdc++.h> # define fi first # define se second using namespace std; struct segtree { segtree* L; segtree* R; int val; segtree(int x) { val = x; L = R = NULL; } }; segtree* root; segtree* info[100001]; segtree* upd(int lf, int rg, segtree* nw, int pos) { segtree* nl = new segtree(0); if(lf == rg) { nl->val = 1; } else { int mid = (lf + rg) / 2; if(pos <= mid) { if(nw->L == NULL) nw->L = new segtree(0); nl->R = nw->R; nl->L = upd(lf, mid, nw->L, pos); } else { nl->L = nw->L; if(nw->R == NULL) nw->R = new segtree(0); nl->R = upd(mid+1, rg, nw->R, pos); } nl->val = 0; if(nl->L != NULL) nl->val += nl->L->val; if(nl->R != NULL) nl->val += nl->R->val; } return nl; } int N, M; segtree* merge(int lf, int rg, segtree* a, segtree* b) { if(a == NULL || !a->val) return b; if(b == NULL || !b->val) return a; if(a == b || lf == rg) return a; segtree* c = new segtree(0); int mid = (lf + rg) / 2; c->L = merge(lf, mid, a->L, b->L); c->R = merge(mid+1, rg, a->R, b->R); if(c->L != NULL) c->val += c->L->val; if(c->R != NULL) c->val += c->R->val; return c; } int Q, dpt[100001], sz[100001], mx[100001], bg[100001], pos[100001], par[100001], in[100001], rt[100001], t; vector< pair<int, int> > sp; vector<int> edge[100001]; bool tr[100001]; void dfs(int a, int pr, int dt) { par[a] = pr; dpt[a] = dt; sz[a] = 1; mx[a] = -1; bg[a] = -1; for(int i=0;i<edge[a].size();i++) { if(edge[a][i] == pr) continue; dfs(edge[a][i], a, dt+1); sz[a] += sz[edge[a][i]]; if(mx[a] < sz[edge[a][i]]) { mx[a] = sz[edge[a][i]]; bg[a] = edge[a][i]; } } } void build_hld(int a, int pr, int root) { rt[a] = root; pos[t] = a; in[a] = t++; rt[a] = root; if(bg[a] != -1) build_hld(bg[a], a, root); for(int i=0;i<edge[a].size();i++) { if(edge[a][i] == pr || edge[a][i] == bg[a]) continue; if(edge[a][i] == bg[a]) continue; build_hld(edge[a][i], a, a); } } int fen[100001]; void add(int a, int x) { while(a <= 1e5) { fen[a] += x; a += a&(-a); } } int qry(int a) { int as = 0; while(a > 0) { as += fen[a]; a -= a&(-a); } return as; } int binser(int a) { int id = 0, sum = 0; for(int i=20;i>=0;i--) { id += (1 << i); if(id <= 1e5 && sum + fen[id] <= a) { sum += fen[id]; } else { id -= (1 << i); } } return id; } int find(int a) { while(true) { int L = qry(1e5 - in[a] - 1); L = binser(L); // cout<<"L : "<<L<<endl; // if(a != 0) cout<<a<<" "<<L<<" "<<rt[a]<<endl; if(L >= 1e5 - in[rt[a]]) a = par[rt[a]]; else { L++; return pos[(int) 1e5 - L]; } } } int main() { scanf("%d %d %d", &N, &M, &Q); for(int i=1;i<N;i++) { int a, b; scanf("%d %d", &a, &b); edge[a].push_back(b); edge[b].push_back(a); sp.push_back(make_pair(a, b)); } dfs(1, 0, 0); build_hld(1, 0, 1); root = new segtree(0); for(int i=1;i<=N;i++) { add(1e5 - in[i], 1); info[i] = upd(1, N, root, i); } for(int i=0;i<M;i++) { int L; scanf("%d", &L); L--; if(dpt[sp[L].fi] < dpt[sp[L].se]) swap(sp[L].fi, sp[L].se); if(!tr[L]) { // sambungin L tr[L] = 1; // cout<<"sp : "<<sp[L].se<<" "<<find(sp[L].se)<<endl; int KL = find(sp[L].se); info[KL] = merge(1, N, info[sp[L].fi], info[KL]); add(1e5 - in[sp[L].fi], -1); } else { // dipisah tr[L] = 0; // cout<<"sp : "<<sp[L].se<<" "<<find(sp[L].se)<<" "<<sp[L].fi<<" "<<info[find(sp[L].se)].count()<<endl; info[sp[L].fi] = info[find(sp[L].se)]; add(1e5 - in[sp[L].fi], 1); } // for(int i=1;i<=N;i++) cout<<info[find(i)].count()<<" "; // cout<<endl; } while(Q--) { int v; scanf("%d", &v); printf("%d\n", info[find(v)]->val); } }

Compilation message (stderr)

synchronization.cpp: In function 'void dfs(int, int, int)':
synchronization.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i=0;i<edge[a].size();i++) {
      |              ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'void build_hld(int, int, int)':
synchronization.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i=0;i<edge[a].size();i++) {
      |              ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |  scanf("%d %d %d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |   scanf("%d", &L);
      |   ~~~~~^~~~~~~~~~
synchronization.cpp:179:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |   scanf("%d", &v);
      |   ~~~~~^~~~~~~~~~
#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...