oj.uz

Submission #392298

# Submission time Handle Problem Language Result Execution time Memory
392298 2021-04-20T19:05:51 Z achibasadzishvili Regions (IOI09_regions) C++17
60 / 100
 8000 ms 131076 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];
vector<ll>v[N],g[N];
int ans[1505][26000],rev[1505][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);
}
int main(){
    cin >> n >> r >> q;
    sq = n / 1500;
    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]){
            t[pown + in[a] - 1]++;
            upd((pown + in[a] - 1) / 2);
        }
        ll ret = 0;
        for(auto a : g[x]){
            ret += get(1 , 1 , pown , in[a] , out[a]);
        }
        for(auto a : g[y]){
            t[pown + in[a] - 1]--;
            upd((pown + in[a] - 1) / 2);
        }
        cout << ret << endl;
    }
    
    
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:61:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         if(g[i].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
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[x].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
regions.cpp:81:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |         if(g[y].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9740 KB Output is correct
2 Correct 9 ms 9672 KB Output is correct
3 Correct 9 ms 9800 KB Output is correct
4 Correct 15 ms 9980 KB Output is correct
5 Correct 16 ms 10056 KB Output is correct
6 Correct 25 ms 12360 KB Output is correct
7 Correct 38 ms 11160 KB Output is correct
8 Correct 36 ms 11800 KB Output is correct
9 Correct 100 ms 13416 KB Output is correct
10 Correct 207 ms 15060 KB Output is correct
11 Correct 277 ms 13392 KB Output is correct
12 Correct 299 ms 16468 KB Output is correct
13 Correct 450 ms 14488 KB Output is correct
14 Correct 411 ms 13192 KB Output is correct
15 Correct 459 ms 16940 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1256 ms 16712 KB Output is correct
2 Correct 1176 ms 15736 KB Output is correct
3 Correct 2153 ms 19704 KB Output is correct
4 Correct 470 ms 15540 KB Output is correct
5 Correct 746 ms 32704 KB Output is correct
6 Correct 753 ms 16980 KB Output is correct
7 Correct 1363 ms 24768 KB Output is correct
8 Correct 1782 ms 55340 KB Output is correct
9 Execution timed out 8029 ms 96012 KB Time limit exceeded
10 Runtime error 2994 ms 131076 KB Execution killed with signal 9
11 Runtime error 7481 ms 131072 KB Execution killed with signal 9
12 Execution timed out 8093 ms 71680 KB Time limit exceeded
13 Execution timed out 8085 ms 94880 KB Time limit exceeded
14 Execution timed out 8093 ms 86860 KB Time limit exceeded
15 Runtime error 5530 ms 131076 KB Execution killed with signal 9
16 Runtime error 3799 ms 131076 KB Execution killed with signal 9
17 Correct 6119 ms 119388 KB Output is correct