oj.uz

Submission #908970

# Submission time Handle Problem Language Result Execution time Memory
908970 2024-01-17T03:57:23 Z 089487 Regions (IOI09_regions) C++14
100 / 100
 6165 ms 131036 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=600;
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 7 ms 25432 KB Output is correct
2 Correct 6 ms 25528 KB Output is correct
3 Correct 8 ms 25432 KB Output is correct
4 Correct 9 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 23 ms 25432 KB Output is correct
8 Correct 24 ms 25432 KB Output is correct
9 Correct 36 ms 25944 KB Output is correct
10 Correct 66 ms 25944 KB Output is correct
11 Correct 134 ms 26260 KB Output is correct
12 Correct 125 ms 26628 KB Output is correct
13 Correct 190 ms 26284 KB Output is correct
14 Correct 383 ms 26840 KB Output is correct
15 Correct 346 ms 28284 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1582 ms 56512 KB Output is correct
2 Correct 1856 ms 51116 KB Output is correct
3 Correct 3260 ms 64424 KB Output is correct
4 Correct 339 ms 26692 KB Output is correct
5 Correct 331 ms 27792 KB Output is correct
6 Correct 2064 ms 27680 KB Output is correct
7 Correct 2720 ms 28104 KB Output is correct
8 Correct 2397 ms 31924 KB Output is correct
9 Correct 3445 ms 33788 KB Output is correct
10 Correct 6165 ms 37664 KB Output is correct
11 Correct 6059 ms 33048 KB Output is correct
12 Correct 1559 ms 42372 KB Output is correct
13 Correct 2177 ms 44932 KB Output is correct
14 Correct 2545 ms 82268 KB Output is correct
15 Correct 4342 ms 49724 KB Output is correct
16 Correct 3711 ms 60952 KB Output is correct
17 Correct 3509 ms 131036 KB Output is correct