oj.uz

Submission #392292

# Submission time Handle Problem Language Result Execution time Memory
392292 2021-04-20T18:55:30 Z achibasadzishvili Regions (IOI09_regions) C++17
13 / 100
 8000 ms 70344 KB 
#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 230000;
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[250][26000],rev[250][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[y][c[x]] += ch[x];
        ans[y][c[x]] += cur;
    }
    cur -= (c[x] == y);
}
int main(){
    cin >> n >> r >> q;
    sq = n / 250;
    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
8.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11080 KB Output is correct
2 Correct 8 ms 11208 KB Output is correct
3 Correct 11 ms 11208 KB Output is correct
4 Correct 13 ms 11336 KB Output is correct
5 Correct 12 ms 11464 KB Output is correct
6 Runtime error 46 ms 27072 KB Execution killed with signal 11
7 Incorrect 47 ms 12672 KB Output isn't correct
8 Incorrect 33 ms 13084 KB Output isn't correct
9 Runtime error 86 ms 26040 KB Execution killed with signal 11
10 Incorrect 155 ms 11720 KB Output isn't correct
11 Runtime error 73 ms 27044 KB Execution killed with signal 11
12 Correct 363 ms 12488 KB Output is correct
13 Correct 475 ms 12148 KB Output is correct
14 Correct 404 ms 14756 KB Output is correct
15 Incorrect 416 ms 18476 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3457 ms 17168 KB Output isn't correct
2 Incorrect 3606 ms 15680 KB Output isn't correct
3 Execution timed out 8048 ms 19220 KB Time limit exceeded
4 Runtime error 58 ms 27540 KB Execution killed with signal 11
5 Correct 1057 ms 14144 KB Output is correct
6 Runtime error 60 ms 28884 KB Execution killed with signal 11
7 Runtime error 87 ms 31512 KB Execution killed with signal 11
8 Runtime error 136 ms 44592 KB Execution killed with signal 11
9 Execution timed out 8090 ms 20796 KB Time limit exceeded
10 Execution timed out 8068 ms 24696 KB Time limit exceeded
11 Execution timed out 8066 ms 21080 KB Time limit exceeded
12 Runtime error 224 ms 43200 KB Execution killed with signal 11
13 Runtime error 172 ms 43128 KB Execution killed with signal 11
14 Runtime error 234 ms 46312 KB Execution killed with signal 11
15 Runtime error 182 ms 49600 KB Execution killed with signal 11
16 Runtime error 241 ms 70344 KB Execution killed with signal 11
17 Runtime error 206 ms 68484 KB Execution killed with signal 11