oj.uz

Submission #908966

# Submission time Handle Problem Language Result Execution time Memory
908966 2024-01-17T03:48:32 Z 089487 Regions (IOI09_regions) C++14
95 / 100
 7142 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=4e5+2;
const int INF=1e18;
const int K=500;
const int K2=400;
vector<int> cnt[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){
    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;
}
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;
        }
    }
    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;
    }
}

Compilation message

regions.cpp:23:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 | const int INF=1e18;
      |               ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25432 KB Output is correct
2 Correct 7 ms 25432 KB Output is correct
3 Correct 8 ms 25432 KB Output is correct
4 Correct 10 ms 25684 KB Output is correct
5 Correct 13 ms 25432 KB Output is correct
6 Correct 19 ms 25684 KB Output is correct
7 Correct 25 ms 25432 KB Output is correct
8 Correct 28 ms 25432 KB Output is correct
9 Correct 42 ms 25944 KB Output is correct
10 Correct 75 ms 25944 KB Output is correct
11 Correct 137 ms 26256 KB Output is correct
12 Correct 141 ms 26620 KB Output is correct
13 Correct 216 ms 26288 KB Output is correct
14 Correct 412 ms 26780 KB Output is correct
15 Correct 390 ms 28248 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1637 ms 68164 KB Output is correct
2 Correct 1831 ms 56460 KB Output is correct
3 Correct 3494 ms 64668 KB Output is correct
4 Correct 353 ms 26696 KB Output is correct
5 Correct 413 ms 27800 KB Output is correct
6 Correct 1464 ms 49448 KB Output is correct
7 Correct 2954 ms 28108 KB Output is correct
8 Correct 2780 ms 45324 KB Output is correct
9 Correct 4382 ms 33932 KB Output is correct
10 Correct 7142 ms 37260 KB Output is correct
11 Correct 6262 ms 33268 KB Output is correct
12 Correct 1495 ms 42188 KB Output is correct
13 Correct 2095 ms 45088 KB Output is correct
14 Correct 2293 ms 87260 KB Output is correct
15 Correct 3813 ms 49732 KB Output is correct
16 Correct 3338 ms 60868 KB Output is correct
17 Runtime error 241 ms 131072 KB Execution killed with signal 9