oj.uz

Submission #392309

# Submission time Handle Problem Language Result Execution time Memory
392309 2021-04-20T19:17:11 Z achibasadzishvili Regions (IOI09_regions) C++17
95 / 100
 8000 ms 104404 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
regions.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
regions.cpp: In function 'int main()':
regions.cpp:82:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |         if(g[i].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
regions.cpp:98:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |         if(g[x].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
regions.cpp:102:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |         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 7 ms 9800 KB Output is correct
3 Correct 9 ms 9800 KB Output is correct
4 Correct 12 ms 10056 KB Output is correct
5 Correct 15 ms 10056 KB Output is correct
6 Correct 37 ms 12232 KB Output is correct
7 Correct 42 ms 11208 KB Output is correct
8 Correct 60 ms 11784 KB Output is correct
9 Correct 81 ms 13456 KB Output is correct
10 Correct 238 ms 15168 KB Output is correct
11 Correct 265 ms 13404 KB Output is correct
12 Correct 380 ms 16760 KB Output is correct
13 Correct 450 ms 14472 KB Output is correct
14 Correct 407 ms 13240 KB Output is correct
15 Correct 433 ms 16912 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 16600 KB Output is correct
2 Correct 1466 ms 15236 KB Output is correct
3 Correct 1897 ms 19548 KB Output is correct
4 Correct 398 ms 15680 KB Output is correct
5 Correct 707 ms 31080 KB Output is correct
6 Correct 936 ms 16648 KB Output is correct
7 Correct 1051 ms 23308 KB Output is correct
8 Correct 1572 ms 28956 KB Output is correct
9 Correct 3264 ms 32496 KB Output is correct
10 Correct 3481 ms 46524 KB Output is correct
11 Execution timed out 8048 ms 104404 KB Time limit exceeded
12 Correct 2129 ms 21696 KB Output is correct
13 Correct 3045 ms 22080 KB Output is correct
14 Correct 3394 ms 25228 KB Output is correct
15 Correct 5233 ms 26976 KB Output is correct
16 Correct 5156 ms 41152 KB Output is correct
17 Correct 5037 ms 36236 KB Output is correct