oj.uz

Submission #392294

# Submission time Handle Problem Language Result Execution time Memory
392294 2021-04-20T18:59:36 Z achibasadzishvili Regions (IOI09_regions) C++17
75 / 100
 8000 ms 47180 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[500][26000],rev[500][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 / 500;
    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 9800 KB Output is correct
3 Correct 9 ms 9800 KB Output is correct
4 Correct 10 ms 9928 KB Output is correct
5 Correct 14 ms 10060 KB Output is correct
6 Correct 28 ms 12232 KB Output is correct
7 Correct 36 ms 11208 KB Output is correct
8 Correct 45 ms 11720 KB Output is correct
9 Correct 60 ms 13488 KB Output is correct
10 Correct 181 ms 14232 KB Output is correct
11 Correct 221 ms 13352 KB Output is correct
12 Correct 319 ms 15296 KB Output is correct
13 Correct 398 ms 14508 KB Output is correct
14 Correct 410 ms 13200 KB Output is correct
15 Correct 392 ms 16868 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1226 ms 16608 KB Output is correct
2 Correct 1735 ms 15676 KB Output is correct
3 Correct 2117 ms 19636 KB Output is correct
4 Correct 337 ms 15552 KB Output is correct
5 Correct 697 ms 18452 KB Output is correct
6 Correct 864 ms 16908 KB Output is correct
7 Correct 1627 ms 21312 KB Output is correct
8 Correct 2110 ms 29248 KB Output is correct
9 Execution timed out 8036 ms 27100 KB Time limit exceeded
10 Correct 6744 ms 47180 KB Output is correct
11 Execution timed out 8037 ms 19628 KB Time limit exceeded
12 Correct 4579 ms 22404 KB Output is correct
13 Correct 6525 ms 22848 KB Output is correct
14 Correct 6542 ms 25904 KB Output is correct
15 Execution timed out 8023 ms 27684 KB Time limit exceeded
16 Execution timed out 8007 ms 35172 KB Time limit exceeded
17 Execution timed out 8041 ms 37028 KB Time limit exceeded