oj.uz

Submission #909187

# Submission time Handle Problem Language Result Execution time Memory
909187 2024-01-17T06:05:28 Z 089487 Regions (IOI09_regions) C++14
90 / 100
 1759 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=2e5+2;
const int M=25e3+7;
const int K=450;
const int K2=450;
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 8280 KB Output is correct
2 Correct 3 ms 8280 KB Output is correct
3 Correct 3 ms 8280 KB Output is correct
4 Correct 4 ms 8280 KB Output is correct
5 Correct 6 ms 8280 KB Output is correct
6 Correct 12 ms 8280 KB Output is correct
7 Correct 19 ms 8280 KB Output is correct
8 Correct 20 ms 8280 KB Output is correct
9 Correct 25 ms 8792 KB Output is correct
10 Correct 43 ms 8792 KB Output is correct
11 Correct 57 ms 9048 KB Output is correct
12 Correct 65 ms 11608 KB Output is correct
13 Correct 97 ms 11604 KB Output is correct
14 Correct 120 ms 12120 KB Output is correct
15 Correct 122 ms 14368 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 51944 KB Output is correct
2 Correct 789 ms 33664 KB Output is correct
3 Correct 1098 ms 42944 KB Output is correct
4 Correct 127 ms 12120 KB Output is correct
5 Correct 189 ms 13656 KB Output is correct
6 Correct 422 ms 68796 KB Output is correct
7 Correct 626 ms 28776 KB Output is correct
8 Runtime error 215 ms 131072 KB Execution killed with signal 9
9 Correct 965 ms 19552 KB Output is correct
10 Runtime error 336 ms 131072 KB Execution killed with signal 9
11 Correct 1759 ms 19200 KB Output is correct
12 Correct 735 ms 27596 KB Output is correct
13 Correct 895 ms 28512 KB Output is correct
14 Correct 1391 ms 66920 KB Output is correct
15 Correct 1338 ms 35480 KB Output is correct
16 Correct 1353 ms 46160 KB Output is correct
17 Correct 1527 ms 96760 KB Output is correct