oj.uz

Submission #392295

# Submission time Handle Problem Language Result Execution time Memory
392295 2021-04-20T19:02:10 Z achibasadzishvili Regions (IOI09_regions) C++17
80 / 100
 8000 ms 56460 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[700][26000],rev[700][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 / 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]){
            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 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 9 ms 9800 KB Output is correct
4 Correct 11 ms 9932 KB Output is correct
5 Correct 19 ms 10056 KB Output is correct
6 Correct 27 ms 12232 KB Output is correct
7 Correct 27 ms 11208 KB Output is correct
8 Correct 61 ms 11720 KB Output is correct
9 Correct 75 ms 13384 KB Output is correct
10 Correct 226 ms 15072 KB Output is correct
11 Correct 266 ms 13384 KB Output is correct
12 Correct 360 ms 16476 KB Output is correct
13 Correct 469 ms 14496 KB Output is correct
14 Correct 419 ms 13200 KB Output is correct
15 Correct 362 ms 16868 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1383 ms 16700 KB Output is correct
2 Correct 1524 ms 15652 KB Output is correct
3 Correct 2088 ms 19520 KB Output is correct
4 Correct 449 ms 15552 KB Output is correct
5 Correct 761 ms 23876 KB Output is correct
6 Correct 840 ms 16960 KB Output is correct
7 Correct 1255 ms 22720 KB Output is correct
8 Correct 1839 ms 29256 KB Output is correct
9 Correct 5522 ms 33068 KB Output is correct
10 Correct 6086 ms 47072 KB Output is correct
11 Execution timed out 8071 ms 56460 KB Time limit exceeded
12 Correct 4345 ms 22468 KB Output is correct
13 Correct 6424 ms 22824 KB Output is correct
14 Correct 6264 ms 25924 KB Output is correct
15 Execution timed out 8038 ms 27732 KB Time limit exceeded
16 Execution timed out 8028 ms 35136 KB Time limit exceeded
17 Execution timed out 8079 ms 37008 KB Time limit exceeded