oj.uz

Submission #392288

# Submission time Handle Problem Language Result Execution time Memory
392288 2021-04-20T18:49:00 Z achibasadzishvili Regions (IOI09_regions) C++17
60 / 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 = 230000;
ll n,r,q,sq,pown = 1;
ll timer,in[N],out[N],t[4 * N],cur,c[N],p[N],ch[N];
vector<ll>v[N],g[N];
map<int,int>ans[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){
        ans[c[x]][y] += ch[x];
        ans[y][c[x]] += cur;
    }
    cur -= (c[x] == y);
}
int main(){
    cin >> n >> r >> q;
    sq = sqrt(n);
    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);
        }
    }
    
    for(auto a : big){
        for(int i=1; i<=r; i++)
            ans[a][i] = ans[i][a] = 0;
        solve(1 , a);
    }
    
    while(q--){
        ll x,y;
        cin >> x >> y;
        if(g[x].size() >= sq || g[y].size() >= sq){
            cout << ans[x][y] << 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:75:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         if(g[x].size() >= sq || g[y].size() >= sq){
      |            ~~~~~~~~~~~~^~~~~
regions.cpp:75:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         if(g[x].size() >= sq || g[y].size() >= sq){
      |                                 ~~~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12232 KB Output is correct
2 Correct 8 ms 12360 KB Output is correct
3 Correct 10 ms 12272 KB Output is correct
4 Correct 16 ms 12332 KB Output is correct
5 Correct 20 ms 12360 KB Output is correct
6 Correct 37 ms 12360 KB Output is correct
7 Correct 47 ms 12360 KB Output is correct
8 Correct 44 ms 12360 KB Output is correct
9 Correct 79 ms 12744 KB Output is correct
10 Correct 149 ms 12872 KB Output is correct
11 Correct 303 ms 13192 KB Output is correct
12 Correct 356 ms 13712 KB Output is correct
13 Correct 501 ms 13368 KB Output is correct
14 Correct 833 ms 14272 KB Output is correct
15 Correct 1182 ms 19264 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3831 ms 19020 KB Output is correct
2 Correct 4324 ms 16960 KB Output is correct
3 Execution timed out 8050 ms 22020 KB Time limit exceeded
4 Correct 768 ms 14016 KB Output is correct
5 Correct 955 ms 15340 KB Output is correct
6 Correct 2190 ms 55388 KB Output is correct
7 Correct 3708 ms 63928 KB Output is correct
8 Correct 7885 ms 119992 KB Output is correct
9 Execution timed out 8058 ms 22068 KB Time limit exceeded
10 Runtime error 4417 ms 131076 KB Execution killed with signal 9
11 Execution timed out 8038 ms 22244 KB Time limit exceeded
12 Correct 4592 ms 27968 KB Output is correct
13 Correct 6621 ms 29060 KB Output is correct
14 Execution timed out 8057 ms 66600 KB Time limit exceeded
15 Execution timed out 8070 ms 37992 KB Time limit exceeded
16 Execution timed out 8055 ms 50904 KB Time limit exceeded
17 Execution timed out 8064 ms 86812 KB Time limit exceeded