oj.uz

Submission #392305

# Submission time Handle Problem Language Result Execution time Memory
392305 2021-04-20T19:12:24 Z achibasadzishvili Regions (IOI09_regions) C++17
95 / 100
 8000 ms 104412 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],t[4 * 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 upd(ll x){
    if(!x)return;
    t[x] = t[2 * x] + t[2 * x + 1];
    upd(x / 2);
}
ll get(ll x,ll L,ll R,ll l,ll r){
    if(L > r || R < l)return 0;
    if(L >= l && R <= r)return t[x];
    ll k1 = get(2 * x , L , (L + R) / 2 , l , r);
    ll k2 = get(2 * x + 1 , (L + R) / 2 + 1 , R , l , r);
    return k1 + k2;
}
*/
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 = n / 800;
    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:77:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |         if(g[i].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
regions.cpp:93:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |         if(g[x].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
regions.cpp:97:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |         if(g[y].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9800 KB Output is correct
3 Correct 8 ms 9800 KB Output is correct
4 Correct 8 ms 10056 KB Output is correct
5 Correct 11 ms 10056 KB Output is correct
6 Correct 38 ms 12232 KB Output is correct
7 Correct 40 ms 11208 KB Output is correct
8 Correct 46 ms 11848 KB Output is correct
9 Correct 95 ms 13504 KB Output is correct
10 Correct 235 ms 15136 KB Output is correct
11 Correct 277 ms 13404 KB Output is correct
12 Correct 377 ms 16428 KB Output is correct
13 Correct 470 ms 14416 KB Output is correct
14 Correct 420 ms 13248 KB Output is correct
15 Correct 410 ms 17088 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1281 ms 16684 KB Output is correct
2 Correct 1384 ms 15236 KB Output is correct
3 Correct 1937 ms 20056 KB Output is correct
4 Correct 343 ms 15508 KB Output is correct
5 Correct 598 ms 30960 KB Output is correct
6 Correct 840 ms 16740 KB Output is correct
7 Correct 1124 ms 23320 KB Output is correct
8 Correct 1412 ms 28888 KB Output is correct
9 Correct 3612 ms 32532 KB Output is correct
10 Correct 3252 ms 46632 KB Output is correct
11 Execution timed out 8066 ms 104412 KB Time limit exceeded
12 Correct 1969 ms 21604 KB Output is correct
13 Correct 2692 ms 22068 KB Output is correct
14 Correct 3143 ms 25112 KB Output is correct
15 Correct 4898 ms 26972 KB Output is correct
16 Correct 4957 ms 41176 KB Output is correct
17 Correct 4806 ms 36208 KB Output is correct