oj.uz

Submission #392296

# Submission time Handle Problem Language Result Execution time Memory
392296 2021-04-20T19:04:32 Z achibasadzishvili Regions (IOI09_regions) C++17
65 / 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[1000][26000],rev[1000][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 / 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]){
            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 7 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 13 ms 9928 KB Output is correct
5 Correct 10 ms 10056 KB Output is correct
6 Correct 36 ms 12360 KB Output is correct
7 Correct 39 ms 11164 KB Output is correct
8 Correct 61 ms 11720 KB Output is correct
9 Correct 113 ms 13512 KB Output is correct
10 Correct 216 ms 15088 KB Output is correct
11 Correct 257 ms 13464 KB Output is correct
12 Correct 356 ms 16384 KB Output is correct
13 Correct 439 ms 14400 KB Output is correct
14 Correct 308 ms 13376 KB Output is correct
15 Correct 405 ms 16908 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1211 ms 16660 KB Output is correct
2 Correct 1394 ms 15808 KB Output is correct
3 Correct 1745 ms 19560 KB Output is correct
4 Correct 413 ms 15588 KB Output is correct
5 Correct 664 ms 32664 KB Output is correct
6 Correct 798 ms 16960 KB Output is correct
7 Correct 1396 ms 24056 KB Output is correct
8 Correct 2191 ms 42888 KB Output is correct
9 Correct 6284 ms 65680 KB Output is correct
10 Runtime error 2950 ms 131076 KB Execution killed with signal 9
11 Runtime error 7715 ms 131076 KB Execution killed with signal 9
12 Execution timed out 8087 ms 70544 KB Time limit exceeded
13 Execution timed out 8055 ms 82284 KB Time limit exceeded
14 Correct 6116 ms 27592 KB Output is correct
15 Execution timed out 8041 ms 27776 KB Time limit exceeded
16 Runtime error 3641 ms 131076 KB Execution killed with signal 9
17 Execution timed out 8074 ms 38644 KB Time limit exceeded