oj.uz

Submission #909186

# Submission time Handle Problem Language Result Execution time Memory
909186 2024-01-17T06:04:36 Z 089487 Regions (IOI09_regions) C++14
100 / 100
 1773 ms 105572 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 K=600;
const int K2=400;
vector<int> cnt[N];
vector<int> inc[N];
vector<int> outc[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){
    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 7 ms 22360 KB Output is correct
2 Correct 7 ms 22432 KB Output is correct
3 Correct 8 ms 22360 KB Output is correct
4 Correct 11 ms 22520 KB Output is correct
5 Correct 10 ms 22356 KB Output is correct
6 Correct 13 ms 22616 KB Output is correct
7 Correct 21 ms 22616 KB Output is correct
8 Correct 22 ms 22616 KB Output is correct
9 Correct 29 ms 22872 KB Output is correct
10 Correct 48 ms 22860 KB Output is correct
11 Correct 65 ms 23384 KB Output is correct
12 Correct 66 ms 25824 KB Output is correct
13 Correct 92 ms 25432 KB Output is correct
14 Correct 122 ms 26200 KB Output is correct
15 Correct 125 ms 28540 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 49708 KB Output is correct
2 Correct 798 ms 48220 KB Output is correct
3 Correct 1105 ms 57128 KB Output is correct
4 Correct 145 ms 26148 KB Output is correct
5 Correct 202 ms 27672 KB Output is correct
6 Correct 494 ms 27216 KB Output is correct
7 Correct 658 ms 28292 KB Output is correct
8 Correct 584 ms 33216 KB Output is correct
9 Correct 941 ms 33736 KB Output is correct
10 Correct 1412 ms 38812 KB Output is correct
11 Correct 1773 ms 33556 KB Output is correct
12 Correct 738 ms 40600 KB Output is correct
13 Correct 908 ms 42660 KB Output is correct
14 Correct 1352 ms 73036 KB Output is correct
15 Correct 1398 ms 49628 KB Output is correct
16 Correct 1368 ms 60640 KB Output is correct
17 Correct 1373 ms 105572 KB Output is correct