oj.uz

Submission #908961

# Submission time Handle Problem Language Result Execution time Memory
908961 2024-01-17T03:40:11 Z 089487 Regions (IOI09_regions) C++14
50 / 100
 5630 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];*/
        }
    }
    assert(ID<K);
    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 4 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 5 ms 16560 KB Output is correct
4 Correct 7 ms 16728 KB Output is correct
5 Correct 8 ms 16980 KB Output is correct
6 Correct 15 ms 16880 KB Output is correct
7 Correct 19 ms 16892 KB Output is correct
8 Correct 23 ms 16920 KB Output is correct
9 Correct 40 ms 16984 KB Output is correct
10 Correct 72 ms 17588 KB Output is correct
11 Correct 121 ms 17604 KB Output is correct
12 Correct 138 ms 17936 KB Output is correct
13 Correct 228 ms 17692 KB Output is correct
14 Correct 355 ms 18200 KB Output is correct
15 Correct 325 ms 19764 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1474 ms 84720 KB Output is correct
2 Correct 1794 ms 56844 KB Output is correct
3 Correct 3131 ms 69564 KB Output is correct
4 Correct 316 ms 18088 KB Output is correct
5 Correct 335 ms 19184 KB Output is correct
6 Correct 490 ms 124592 KB Output is correct
7 Correct 2013 ms 49904 KB Output is correct
8 Runtime error 117 ms 131072 KB Execution killed with signal 9
9 Incorrect 3511 ms 26172 KB Output isn't correct
10 Runtime error 191 ms 131072 KB Execution killed with signal 9
11 Incorrect 5630 ms 25660 KB Output isn't correct
12 Incorrect 1421 ms 40008 KB Output isn't correct
13 Incorrect 1971 ms 41244 KB Output isn't correct
14 Incorrect 2431 ms 124780 KB Output isn't correct
15 Incorrect 3498 ms 46080 KB Output isn't correct
16 Incorrect 2540 ms 57144 KB Output isn't correct
17 Runtime error 208 ms 131072 KB Execution killed with signal 9