oj.uz

Submission #908969

# Submission time Handle Problem Language Result Execution time Memory
908969 2024-01-17T03:55:34 Z 089487 Regions (IOI09_regions) C++14
95 / 100
 6470 ms 131072 KB 
#include<bits/stdc++.h>
//#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define F first
#define S second
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=4e5+2;
const int INF=1e18;
const int K=525;
const int K2=400;
vector<int> cnt[N];
int pnt[K2][N];
int chd[K2][N];
int idx[N];
int c[N];
vector<int> v[N];
int in[N],out[N];
int t=1;
void dfs(int x){
    in[x]=t++;
    for(int i:v[x]){
        dfs(i);
    }
    out[x]=t++;
}
void solve(int col,int _id,int x=1){
    if(c[x]==col){
        pnt[_id][x]+=1;
        chd[_id][x]+=1;
    }
    for(int i:v[x]){
        chd[_id][i]+=chd[_id][x];
        solve(col,_id,i);
        pnt[_id][x]+=pnt[_id][i];
    }
}
int bit[N];
void add(int x,int val){
    for(;x<N;x+=lowbit(x)){
        bit[x]+=val;
    }
}
int qry(int x){
    int ret=0;
    for(;x>0;x-=lowbit(x)) ret+=bit[x];
    return ret;
}
int bruforce(int c1,int c2){
    vector<pii> p1;
    vector<pii> p2;
    for(int x:cnt[c1]) p1.eb(in[x],out[x]),add(out[x],1);
    for(int x:cnt[c2]) p2.eb(in[x],out[x]);
    sort(all(p1));
    sort(all(p2));
    int l=0;
    int ans=0;
    rep(i,0,sz(p2)-1){
        while(l<sz(p1)&&p1[l].F<=p2[i].F) {
            add(p1[l++].S,-1);
        }
        ans+=qry(p2[i].S);
    }
    while(l<sz(p1)) {
        add(p1[l++].S,-1);
    }
    return ans;
}
long long cntchild(int Id,int r1){
    long long ans=0;
    for(int j:cnt[r1]){
        ans+=chd[Id][j];
    }
    return ans;
}
long long cntpnt(int Id,int r2){
    long long ans=0;
    for(int j:cnt[r2]){
        ans+=pnt[Id][j];
    }
    return ans;
}
signed main(){
	quick
    
    int n,r,q;
    cin>>n>>r>>q;
    cin>>c[1];
    cnt[c[1]].eb(1);
    rep(i,2,n){
        int p;
        cin>>p>>c[i];
        cnt[c[i]].eb(i);
        v[p].eb(i);
    }
    dfs(1);
    int ID=0;
    rep(i,1,r){
        if(sz(cnt[i])>=K){
            idx[i]=ID++;
            solve(i,ID);
            idx[i]=ID;
            ID+=1;
        }
    }
    while(q--){
        int r1,r2;
        cin>>r1>>r2;
        if(sz(cnt[r1])<K&&sz(cnt[r2])<K){
            cout<<bruforce(r2,r1)<<endl;
        }
        else if(sz(cnt[r1])>sz(cnt[r2])){
            cout<<cntchild(idx[r1],r2)<<endl;
        }
        else cout<<cntpnt(idx[r2],r1)<<endl;
    }
}

Compilation message

regions.cpp:23:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 | const int INF=1e18;
      |               ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25432 KB Output is correct
2 Correct 7 ms 25432 KB Output is correct
3 Correct 7 ms 25536 KB Output is correct
4 Correct 8 ms 25432 KB Output is correct
5 Correct 11 ms 25432 KB Output is correct
6 Correct 16 ms 25432 KB Output is correct
7 Correct 24 ms 25432 KB Output is correct
8 Correct 25 ms 25432 KB Output is correct
9 Correct 39 ms 25944 KB Output is correct
10 Correct 66 ms 25944 KB Output is correct
11 Correct 123 ms 26260 KB Output is correct
12 Correct 126 ms 26632 KB Output is correct
13 Correct 202 ms 26276 KB Output is correct
14 Correct 366 ms 26780 KB Output is correct
15 Correct 348 ms 28116 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1558 ms 65708 KB Output is correct
2 Correct 1742 ms 51116 KB Output is correct
3 Correct 3127 ms 64652 KB Output is correct
4 Correct 311 ms 26692 KB Output is correct
5 Correct 325 ms 27800 KB Output is correct
6 Correct 2007 ms 27408 KB Output is correct
7 Correct 2636 ms 28076 KB Output is correct
8 Correct 2355 ms 31912 KB Output is correct
9 Correct 3475 ms 33788 KB Output is correct
10 Correct 6415 ms 37512 KB Output is correct
11 Correct 6470 ms 33044 KB Output is correct
12 Correct 1517 ms 42172 KB Output is correct
13 Correct 2280 ms 44892 KB Output is correct
14 Correct 2393 ms 87628 KB Output is correct
15 Correct 3927 ms 49944 KB Output is correct
16 Correct 3716 ms 60868 KB Output is correct
17 Runtime error 236 ms 131072 KB Execution killed with signal 9