oj.uz

Submission #392307

# Submission time Handle Problem Language Result Execution time Memory
392307 2021-04-20T19:14:20 Z achibasadzishvili Regions (IOI09_regions) C++14
80 / 100
 8000 ms 131076 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[1005][26000],rev[1005][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 / 1000;
    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 8 ms 9916 KB Output is correct
3 Correct 9 ms 9800 KB Output is correct
4 Correct 10 ms 10056 KB Output is correct
5 Correct 16 ms 10116 KB Output is correct
6 Correct 37 ms 12360 KB Output is correct
7 Correct 51 ms 11208 KB Output is correct
8 Correct 55 ms 11776 KB Output is correct
9 Correct 60 ms 13504 KB Output is correct
10 Correct 227 ms 15124 KB Output is correct
11 Correct 268 ms 13324 KB Output is correct
12 Correct 397 ms 16436 KB Output is correct
13 Correct 469 ms 14440 KB Output is correct
14 Correct 408 ms 13252 KB Output is correct
15 Correct 427 ms 16960 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1302 ms 16624 KB Output is correct
2 Correct 1323 ms 15348 KB Output is correct
3 Correct 2033 ms 19564 KB Output is correct
4 Correct 286 ms 15424 KB Output is correct
5 Correct 712 ms 32448 KB Output is correct
6 Correct 738 ms 16652 KB Output is correct
7 Correct 1337 ms 23812 KB Output is correct
8 Correct 1854 ms 42544 KB Output is correct
9 Correct 5885 ms 65020 KB Output is correct
10 Runtime error 2917 ms 131076 KB Execution killed with signal 9
11 Runtime error 7578 ms 131076 KB Execution killed with signal 9
12 Execution timed out 8048 ms 72472 KB Time limit exceeded
13 Correct 7346 ms 81524 KB Output is correct
14 Correct 3244 ms 26760 KB Output is correct
15 Correct 4837 ms 26968 KB Output is correct
16 Runtime error 3490 ms 131076 KB Execution killed with signal 9
17 Correct 4672 ms 37904 KB Output is correct