Submission #536069

#TimeUsernameProblemLanguageResultExecution timeMemory
53606979brueInside information (BOI21_servers)C++14
52.50 / 100
680 ms265312 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Fenwick { int n = 300000; int tree[300002]; void add(int x, int v){ while(x<=n){ tree[x] += v; x += x&-x; } } int sum(int x){ int ret = 0; while(x){ ret += tree[x]; x -= x&-x; } return ret; } int sum(int l, int r){ return sum(r) - sum(l-1); } } tree; int n, q; char qt[300002]; int qa[300002], qb[300002]; int qans[300002]; vector<pair<int, int> > link[300002]; vector<int> increasingVec[300002]; void makeCentroidTree(); bool query(int, int, int); void query(int, int); void processQueries(); int main(){ scanf("%d %d", &n, &q); q += n-1; for(int i=1; i<=q; i++){ scanf(" %c %d", &qt[i], &qa[i]); if(qt[i]!='C') scanf("%d", &qb[i]); if(qt[i]=='S') link[qa[i]].push_back(make_pair(qb[i], i)), link[qb[i]].push_back(make_pair(qa[i], i)); } for(int i=1; i<=n; i++){ sort(link[i].begin(), link[i].end(), [&](auto x, auto y){ return x.second < y.second; }); } makeCentroidTree(); for(int i=1; i<=q; i++){ if(qt[i] == 'C'){ query(qa[i], i); qans[i] += upper_bound(increasingVec[qa[i]].begin(), increasingVec[qa[i]].end(), i) - increasingVec[qa[i]].begin(); qans[i] += 1; } } processQueries(); for(int i=1; i<=q; i++){ if(qt[i]=='S') continue; if(qt[i]=='Q'){ printf("%s\n", query(qa[i], qb[i], i) ? "yes" : "no"); } else{ printf("%d\n", qans[i]); } } } int centroidRoot; vector<int> centroidChild[300002]; int centroidDepth[300002], centroidPar[300002], centroidAncestor[300002][20]; bool centroidUsed[300002]; int subTreeSize[300002]; bool increasing[300002][20], decreasing[300002][20]; int rootLinkWeight[300002][20], parWeight[300002][20]; int rootLink[300002][20]; vector<pair<int, int> > vec[300002]; vector<pair<int, int> > vecSpecific[300002][20]; struct Query { int t; /// 0: 점 추가, 1: 쿼리 int x, y, w, i; Query(){} Query(int t, int x, int y, int w, int i): t(t), x(x), y(y), w(w), i(i){} bool operator<(const Query &r)const{ if(y==r.y) return t<r.t; return y<r.y; } }; vector<Query> queries[300002]; void subTreeDfs(int x, int p=-1){ subTreeSize[x] = 1; for(auto y: link[x]){ if(y.first==p || centroidUsed[y.first]) continue; subTreeDfs(y.first, x); subTreeSize[x] += subTreeSize[y.first]; } } void getCentroid(int x, int p, int &c, int lim){ if(subTreeSize[x] < lim) return; c = x; for(auto y: link[x]){ if(y.first==p || centroidUsed[y.first]) continue; getCentroid(y.first, x, c, lim); } } void makeDatabase(int x, int p, int dp, int parWeight1, int rootWeight1, bool inc, bool dec, int root, int underRoot){ increasing[x][dp] = inc, decreasing[x][dp] = dec; rootLinkWeight[x][dp] = rootWeight1, parWeight[x][dp] = parWeight1; rootLink[x][dp] = underRoot; if(inc){ vec[root].push_back(make_pair(rootWeight1, parWeight1)); vecSpecific[underRoot][dp].push_back(make_pair(rootWeight1, parWeight1)); increasingVec[root].push_back(parWeight1); } for(auto y: link[x]){ if(y.first==p || centroidUsed[y.first]) continue; makeDatabase(y.first, x, dp, y.second, rootWeight1, inc && parWeight1 < y.second, dec && parWeight1 > y.second, root, underRoot); } } int findCentroid(int x, int dp=0){ subTreeDfs(x); int s = subTreeSize[x]; int c = x, lim = (s+1)/2; getCentroid(x, -1, c, lim); centroidUsed[c] = 1; centroidDepth[c] = dp; for(auto y: link[c]){ if(centroidUsed[y.first]) continue; makeDatabase(y.first, c, dp, y.second, y.second, 1, 1, c, y.first); } for(auto y: link[c]){ if(centroidUsed[y.first]) continue; int tmp = findCentroid(y.first, dp+1); centroidPar[tmp] = c; centroidChild[c].push_back(tmp); } return c; } void makeCentroidTree(){ centroidRoot = findCentroid(1); for(int i=1; i<=n; i++) centroidAncestor[i][centroidDepth[i]] = i; for(int i=1; i<=n; i++){ int dp = centroidDepth[i]; for(int j=dp-1; j>=0; j--) centroidAncestor[i][j] = centroidPar[centroidAncestor[i][j+1]]; } } bool query(int A, int B, int i){ if(A==B) return true; swap(A, B); int d=min(centroidDepth[A], centroidDepth[B]); while(centroidAncestor[A][d] != centroidAncestor[B][d]) d--; int root = centroidAncestor[A][d]; if(root == A) return increasing[B][d] && parWeight[B][d] <= i; if(root == B) return decreasing[A][d] && rootLinkWeight[A][d] <= i; return decreasing[A][d] && increasing[B][d] && rootLinkWeight[A][d] < rootLinkWeight[B][d] && parWeight[B][d] <= i; } void query(int x, int i){ for(int d=centroidDepth[x]-1; d>=0; d--){ if(!decreasing[x][d]) continue; if(i >= rootLinkWeight[x][d]) qans[i]++; queries[centroidAncestor[x][d]].push_back(Query(1, rootLinkWeight[x][d]+1, i, 1, i)); } } void processQueries(){ for(int i=1; i<=n; i++){ sort(vec[i].begin(), vec[i].end()); for(int d=0; d<20; d++){ sort(vecSpecific[i][d].begin(), vecSpecific[i][d].end()); } } for(int i=1; i<=n; i++){ vector<Query> qvec = queries[i]; for(pair<int, int> p: vec[i]) qvec.push_back(Query(0, p.first, p.second, 1, 0)); sort(qvec.begin(), qvec.end()); for(Query query: qvec){ if(query.t == 0) tree.add(query.x, query.w); else qans[query.i] += tree.sum(query.x, tree.n); } for(Query query: qvec){ if(query.t == 0) tree.add(query.x, -query.w); } } }

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf(" %c %d", &qt[i], &qa[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:49:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         if(qt[i]!='C') scanf("%d", &qb[i]);
      |                        ~~~~~^~~~~~~~~~~~~~
#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...
#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...