Submission #392319

#TimeUsernameProblemLanguageResultExecution timeMemory
392319achibasadzishviliRegions (IOI09_regions)C++17
100 / 100
7306 ms46576 KiB
#include<bits/stdc++.h> #define ll int #define f first #define s second #define pb push_back using namespace std; const int N = 200005; ll n,r,q,sq,pown = 1; ll timer,in[N],out[N],cur,c[N],p[N],ch[N],ind[26000],b[N]; vector<ll>v[N],g[N]; int ans[805][26000],rev[805][26000]; void go(ll x){ timer++; in[x] = timer; for(auto to : v[x]){ go(to); } out[x] = timer; } void solve(ll x,ll y){ cur += (c[x] == y); ch[x] = (c[x] == y); for(auto to : v[x]){ solve(to , y); ch[x] += ch[to]; } if(c[x] != y){ rev[ind[y]][c[x]] += ch[x]; ans[ind[y]][c[x]] += cur; } cur -= (c[x] == y); } void add(ll x,ll y){ while(y<=n){ b[y]+=x; y+=y&-y; } } ll sum(ll y){ ll x=0; while(y>0){ x+=b[y]; y-=y&-y; } return x; } int main(){ cin >> n >> r >> q; sq = sqrt(n); vector<int>big; while(pown <= n) pown *= 2; cin >> c[1]; g[c[1]].pb(1); for(int i=2; i<=n; i++){ cin >> p[i] >> c[i]; g[c[i]].pb(i); v[p[i]].pb(i); } go(1); for(int i=1; i<=r; i++){ if(g[i].size() >= sq){ big.pb(i); ind[i] = big.size(); } } for(auto a : big){ for(int i=1; i<=r; i++){ ans[ind[a]][i] = 0; rev[ind[a]][i] = 0; } solve(1 , a); } ll x,y; while(q--){ cin >> x >> y; if(g[x].size() >= sq){ cout << ans[ind[x]][y] << endl; continue; } if(g[y].size() >= sq){ cout << rev[ind[y]][x] << endl; continue; } for(auto a : g[y]){ add(1 , in[a]); } ll ret = 0; for(auto a : g[x]){ ret += sum(out[a]) - sum(in[a] - 1); } for(auto a : g[y]){ add(-1 , in[a]); } cout << ret << endl; } return 0; }

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:63:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         if(g[i].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
regions.cpp:79:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |         if(g[x].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
regions.cpp:83:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         if(g[y].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...