oj.uz

Submission #392301

# Submission time Handle Problem Language Result Execution time Memory
392301 2021-04-20T19:10:12 Z achibasadzishvili Regions (IOI09_regions) C++17
95 / 100
 8000 ms 55860 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[705][26000],rev[705][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 / 700;
    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 9 ms 9800 KB Output is correct
4 Correct 12 ms 9932 KB Output is correct
5 Correct 14 ms 10056 KB Output is correct
6 Correct 38 ms 12232 KB Output is correct
7 Correct 53 ms 11212 KB Output is correct
8 Correct 42 ms 11848 KB Output is correct
9 Correct 79 ms 13428 KB Output is correct
10 Correct 233 ms 15024 KB Output is correct
11 Correct 278 ms 13508 KB Output is correct
12 Correct 360 ms 16464 KB Output is correct
13 Correct 419 ms 14420 KB Output is correct
14 Correct 401 ms 13396 KB Output is correct
15 Correct 410 ms 16868 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 16664 KB Output is correct
2 Correct 1169 ms 15324 KB Output is correct
3 Correct 1827 ms 19564 KB Output is correct
4 Correct 463 ms 15552 KB Output is correct
5 Correct 636 ms 23552 KB Output is correct
6 Correct 798 ms 16708 KB Output is correct
7 Correct 1299 ms 22760 KB Output is correct
8 Correct 1567 ms 28844 KB Output is correct
9 Correct 3633 ms 32452 KB Output is correct
10 Correct 3123 ms 46524 KB Output is correct
11 Execution timed out 8041 ms 55860 KB Time limit exceeded
12 Correct 1960 ms 21676 KB Output is correct
13 Correct 2848 ms 22080 KB Output is correct
14 Correct 3424 ms 25096 KB Output is correct
15 Correct 4839 ms 26972 KB Output is correct
16 Correct 5066 ms 34424 KB Output is correct
17 Correct 4552 ms 36160 KB Output is correct