oj.uz

Submission #392284

# Submission time Handle Problem Language Result Execution time Memory
392284 2021-04-20T18:44:52 Z achibasadzishvili Regions (IOI09_regions) C++17
45 / 100
 4410 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[6 * N],cur,c[N],p[N],ch[N];
vector<ll>v[N],g[N];
unordered_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 / 50);
    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 9 ms 12488 KB Output is correct
2 Correct 9 ms 12488 KB Output is correct
3 Correct 11 ms 12548 KB Output is correct
4 Correct 12 ms 12616 KB Output is correct
5 Correct 19 ms 12616 KB Output is correct
6 Correct 36 ms 14536 KB Output is correct
7 Correct 64 ms 13584 KB Output is correct
8 Correct 68 ms 14448 KB Output is correct
9 Correct 182 ms 16960 KB Output is correct
10 Correct 482 ms 21312 KB Output is correct
11 Correct 474 ms 16576 KB Output is correct
12 Correct 886 ms 23284 KB Output is correct
13 Correct 856 ms 18240 KB Output is correct
14 Correct 619 ms 16036 KB Output is correct
15 Correct 804 ms 20544 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2118 ms 19784 KB Output is correct
2 Correct 2335 ms 19128 KB Output is correct
3 Correct 3218 ms 23344 KB Output is correct
4 Correct 705 ms 51700 KB Output is correct
5 Runtime error 1483 ms 131076 KB Execution killed with signal 9
6 Correct 1363 ms 51136 KB Output is correct
7 Correct 3410 ms 126152 KB Output is correct
8 Runtime error 1893 ms 131076 KB Execution killed with signal 9
9 Runtime error 3462 ms 131076 KB Execution killed with signal 9
10 Runtime error 1700 ms 131076 KB Execution killed with signal 9
11 Runtime error 2753 ms 131076 KB Execution killed with signal 9
12 Runtime error 4410 ms 131076 KB Execution killed with signal 9
13 Runtime error 3438 ms 131076 KB Execution killed with signal 9
14 Runtime error 3651 ms 131076 KB Execution killed with signal 9
15 Runtime error 2401 ms 131076 KB Execution killed with signal 9
16 Runtime error 1949 ms 131076 KB Execution killed with signal 9
17 Runtime error 2013 ms 131076 KB Execution killed with signal 9