oj.uz

Submission #392293

# Submission time Handle Problem Language Result Execution time Memory
392293 2021-04-20T18:55:52 Z achibasadzishvili Regions (IOI09_regions) C++17
13 / 100
 8000 ms 67424 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[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 6 ms 9672 KB Output is correct
2 Correct 7 ms 9856 KB Output is correct
3 Correct 9 ms 9800 KB Output is correct
4 Correct 10 ms 10056 KB Output is correct
5 Correct 15 ms 10056 KB Output is correct
6 Runtime error 43 ms 24128 KB Execution killed with signal 11
7 Incorrect 55 ms 11220 KB Output isn't correct
8 Incorrect 51 ms 11580 KB Output isn't correct
9 Runtime error 93 ms 23232 KB Execution killed with signal 11
10 Incorrect 135 ms 10288 KB Output isn't correct
11 Runtime error 74 ms 24240 KB Execution killed with signal 11
12 Correct 352 ms 11044 KB Output is correct
13 Correct 475 ms 10884 KB Output is correct
14 Correct 405 ms 13312 KB Output is correct
15 Incorrect 439 ms 17176 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3581 ms 15796 KB Output isn't correct
2 Incorrect 4291 ms 14336 KB Output isn't correct
3 Execution timed out 8061 ms 17872 KB Time limit exceeded
4 Runtime error 68 ms 24656 KB Execution killed with signal 11
5 Correct 1059 ms 12752 KB Output is correct
6 Runtime error 81 ms 26016 KB Execution killed with signal 11
7 Runtime error 78 ms 28732 KB Execution killed with signal 11
8 Runtime error 109 ms 41380 KB Execution killed with signal 11
9 Execution timed out 8006 ms 19360 KB Time limit exceeded
10 Execution timed out 8055 ms 23260 KB Time limit exceeded
11 Execution timed out 8021 ms 19640 KB Time limit exceeded
12 Runtime error 177 ms 40384 KB Execution killed with signal 11
13 Runtime error 171 ms 40248 KB Execution killed with signal 11
14 Runtime error 221 ms 43328 KB Execution killed with signal 11
15 Runtime error 180 ms 46784 KB Execution killed with signal 11
16 Runtime error 212 ms 67424 KB Execution killed with signal 11
17 Runtime error 199 ms 65676 KB Execution killed with signal 11