oj.uz

Submission #908959

# Submission time Handle Problem Language Result Execution time Memory
908959 2024-01-17T03:32:47 Z 089487 Regions (IOI09_regions) C++14
50 / 100
 5437 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 INF=1e18;
const int K=450;
vector<int> cnt[N];
int pnt[K][N];
int chd[K][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;
}
int cntchild(int Id,int r1){
    int ans=0;
    for(int j:cnt[r1]){
        ans+=chd[Id][j];
    }
    return ans;
}
int cntpnt(int Id,int r2){
    int 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;
            /*debug("solve","i",i,idx[i],ID,"ID","pnt","chd");
            debug("Col:");for(int j:cnt[i]) cout<<j<<" ";cout<<"\n";
            rep(j,1,n) cout<<pnt[idx[i]][j]<<" \n"[j==n];
            rep(j,1,n) cout<<chd[idx[i]][j]<<" \n"[j==n];*/
        }
    }
    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;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 4 ms 16604 KB Output is correct
3 Correct 6 ms 16728 KB Output is correct
4 Correct 6 ms 16728 KB Output is correct
5 Correct 8 ms 16728 KB Output is correct
6 Correct 14 ms 16860 KB Output is correct
7 Correct 24 ms 16728 KB Output is correct
8 Correct 28 ms 16908 KB Output is correct
9 Correct 34 ms 16984 KB Output is correct
10 Correct 68 ms 17560 KB Output is correct
11 Correct 127 ms 17576 KB Output is correct
12 Correct 137 ms 17924 KB Output is correct
13 Correct 217 ms 17672 KB Output is correct
14 Correct 388 ms 18188 KB Output is correct
15 Correct 370 ms 19808 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1511 ms 84700 KB Output is correct
2 Correct 1680 ms 56828 KB Output is correct
3 Correct 3194 ms 69536 KB Output is correct
4 Correct 312 ms 18068 KB Output is correct
5 Correct 334 ms 19140 KB Output is correct
6 Correct 478 ms 124616 KB Output is correct
7 Correct 2000 ms 49872 KB Output is correct
8 Runtime error 136 ms 131072 KB Execution killed with signal 9
9 Incorrect 3248 ms 26148 KB Output isn't correct
10 Runtime error 227 ms 131072 KB Execution killed with signal 9
11 Incorrect 5437 ms 25516 KB Output isn't correct
12 Incorrect 1451 ms 39988 KB Output isn't correct
13 Incorrect 2004 ms 41116 KB Output isn't correct
14 Incorrect 2249 ms 124972 KB Output isn't correct
15 Incorrect 3455 ms 46056 KB Output isn't correct
16 Incorrect 2749 ms 57348 KB Output isn't correct
17 Runtime error 261 ms 131072 KB Execution killed with signal 9