oj.uz

Submission #392286

# Submission time Handle Problem Language Result Execution time Memory
392286 2021-04-20T18:47:33 Z achibasadzishvili Regions (IOI09_regions) C++17
40 / 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 / 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 8 ms 12232 KB Output is correct
2 Correct 8 ms 12360 KB Output is correct
3 Correct 11 ms 12360 KB Output is correct
4 Correct 14 ms 12360 KB Output is correct
5 Correct 15 ms 12488 KB Output is correct
6 Correct 54 ms 14400 KB Output is correct
7 Correct 81 ms 13464 KB Output is correct
8 Correct 116 ms 14300 KB Output is correct
9 Correct 333 ms 17344 KB Output is correct
10 Correct 1203 ms 21264 KB Output is correct
11 Correct 893 ms 16576 KB Output is correct
12 Correct 2397 ms 23580 KB Output is correct
13 Correct 1899 ms 18844 KB Output is correct
14 Correct 1093 ms 15808 KB Output is correct
15 Correct 1770 ms 22008 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2897 ms 19828 KB Output is correct
2 Correct 3429 ms 19076 KB Output is correct
3 Correct 4996 ms 24340 KB Output is correct
4 Correct 1623 ms 51436 KB Output is correct
5 Runtime error 5187 ms 131076 KB Execution killed with signal 9
6 Correct 2184 ms 55304 KB Output is correct
7 Runtime error 7054 ms 131076 KB Execution killed with signal 9
8 Runtime error 6174 ms 131076 KB Execution killed with signal 9
9 Execution timed out 8055 ms 126784 KB Time limit exceeded
10 Runtime error 4325 ms 131076 KB Execution killed with signal 9
11 Runtime error 6475 ms 131076 KB Execution killed with signal 9
12 Execution timed out 8020 ms 108900 KB Time limit exceeded
13 Execution timed out 8086 ms 122060 KB Time limit exceeded
14 Execution timed out 8013 ms 128580 KB Time limit exceeded
15 Runtime error 5457 ms 131076 KB Execution killed with signal 9
16 Runtime error 4336 ms 131076 KB Execution killed with signal 9
17 Runtime error 5381 ms 131076 KB Execution killed with signal 9