oj.uz

Submission #909192

# Submission time Handle Problem Language Result Execution time Memory
909192 2024-01-17T06:07:42 Z 089487 Regions (IOI09_regions) C++14
100 / 100
 1732 ms 93236 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=2e5+2;
const int M=25e3+7;
const int K=600;
const int K2=400;
vector<int> cnt[M];
vector<int> inc[M];
vector<int> outc[M];
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){
    inc[c[x]].eb(t);
    in[x]=t++;
    for(int i:v[x]){
        dfs(i);
    }
    outc[c[x]].eb(t);
    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];
    }
}
long long bruforce(int c1,int c2){
    int l=0;
    long long ans=0;
    for(int k:outc[c1]){
        while(l<sz(inc[c2])&&inc[c2][l]<k){
            l++;
        }
        ans+=l;
    }
    l=0;
    for(int k:inc[c1]){
        while(l<sz(inc[c2])&&inc[c2][l]<k){
            l++;
        }
        ans-=l;
    }
    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(r1,r2)<<endl;
        }
        else if(sz(cnt[r1])>sz(cnt[r2])){
            cout<<cntchild(idx[r1],r2)<<endl;
        }
        else cout<<cntpnt(idx[r2],r1)<<endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 3 ms 10072 KB Output is correct
3 Correct 4 ms 10072 KB Output is correct
4 Correct 5 ms 10200 KB Output is correct
5 Correct 8 ms 10072 KB Output is correct
6 Correct 13 ms 10072 KB Output is correct
7 Correct 14 ms 10328 KB Output is correct
8 Correct 18 ms 10328 KB Output is correct
9 Correct 24 ms 10584 KB Output is correct
10 Correct 39 ms 10584 KB Output is correct
11 Correct 59 ms 10840 KB Output is correct
12 Correct 82 ms 13400 KB Output is correct
13 Correct 87 ms 13144 KB Output is correct
14 Correct 119 ms 13656 KB Output is correct
15 Correct 137 ms 16348 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 37464 KB Output is correct
2 Correct 829 ms 35896 KB Output is correct
3 Correct 1115 ms 44800 KB Output is correct
4 Correct 144 ms 13912 KB Output is correct
5 Correct 181 ms 15448 KB Output is correct
6 Correct 499 ms 14936 KB Output is correct
7 Correct 627 ms 16044 KB Output is correct
8 Correct 551 ms 20936 KB Output is correct
9 Correct 997 ms 21416 KB Output is correct
10 Correct 1447 ms 26336 KB Output is correct
11 Correct 1732 ms 21068 KB Output is correct
12 Correct 730 ms 28280 KB Output is correct
13 Correct 911 ms 30400 KB Output is correct
14 Correct 1432 ms 60956 KB Output is correct
15 Correct 1310 ms 37308 KB Output is correct
16 Correct 1475 ms 48028 KB Output is correct
17 Correct 1386 ms 93236 KB Output is correct