oj.uz

Submission #392319

# Submission time Handle Problem Language Result Execution time Memory
392319 2021-04-20T19:22:10 Z achibasadzishvili Regions (IOI09_regions) C++17
100 / 100
 7306 ms 46576 KB 
#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

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){
      |            ~~~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 9 ms 9672 KB Output is correct
4 Correct 10 ms 9672 KB Output is correct
5 Correct 20 ms 9672 KB Output is correct
6 Correct 33 ms 9672 KB Output is correct
7 Correct 41 ms 9672 KB Output is correct
8 Correct 57 ms 9800 KB Output is correct
9 Correct 47 ms 10056 KB Output is correct
10 Correct 131 ms 10184 KB Output is correct
11 Correct 114 ms 10440 KB Output is correct
12 Correct 216 ms 10952 KB Output is correct
13 Correct 281 ms 10696 KB Output is correct
14 Correct 421 ms 11440 KB Output is correct
15 Correct 485 ms 14652 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1676 ms 15148 KB Output is correct
2 Correct 2044 ms 13764 KB Output is correct
3 Correct 3722 ms 17276 KB Output is correct
4 Correct 399 ms 11328 KB Output is correct
5 Correct 656 ms 12608 KB Output is correct
6 Correct 879 ms 16628 KB Output is correct
7 Correct 1304 ms 18240 KB Output is correct
8 Correct 1562 ms 28768 KB Output is correct
9 Correct 4429 ms 18728 KB Output is correct
10 Correct 3657 ms 46576 KB Output is correct
11 Correct 7306 ms 18776 KB Output is correct
12 Correct 2033 ms 21608 KB Output is correct
13 Correct 2846 ms 22028 KB Output is correct
14 Correct 3669 ms 25104 KB Output is correct
15 Correct 5478 ms 26952 KB Output is correct
16 Correct 5265 ms 34368 KB Output is correct
17 Correct 4556 ms 36160 KB Output is correct