oj.uz

Submission #908974

# Submission time Handle Problem Language Result Execution time Memory
908974 2024-01-17T04:01:48 Z 089487 Regions (IOI09_regions) C++14
100 / 100
 6366 ms 94504 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=4e5+7;
const int INF=1e18;
const int K=600;
const int K2=344;
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[M];
void add(int x,int val){
    for(;x<M;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;
        }
    }
    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:24:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   24 | const int INF=1e18;
      |               ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15192 KB Output is correct
2 Correct 4 ms 15192 KB Output is correct
3 Correct 5 ms 15192 KB Output is correct
4 Correct 5 ms 15192 KB Output is correct
5 Correct 9 ms 15192 KB Output is correct
6 Correct 12 ms 15192 KB Output is correct
7 Correct 18 ms 15192 KB Output is correct
8 Correct 27 ms 15192 KB Output is correct
9 Correct 35 ms 15704 KB Output is correct
10 Correct 64 ms 15704 KB Output is correct
11 Correct 115 ms 15988 KB Output is correct
12 Correct 136 ms 16360 KB Output is correct
13 Correct 204 ms 16012 KB Output is correct
14 Correct 355 ms 16512 KB Output is correct
15 Correct 373 ms 18012 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1596 ms 37596 KB Output is correct
2 Correct 1755 ms 36232 KB Output is correct
3 Correct 3172 ms 48352 KB Output is correct
4 Correct 332 ms 16416 KB Output is correct
5 Correct 344 ms 17528 KB Output is correct
6 Correct 2052 ms 17276 KB Output is correct
7 Correct 2633 ms 17828 KB Output is correct
8 Correct 2359 ms 21656 KB Output is correct
9 Correct 3663 ms 23516 KB Output is correct
10 Correct 6366 ms 27244 KB Output is correct
11 Correct 6125 ms 22780 KB Output is correct
12 Correct 1521 ms 29288 KB Output is correct
13 Correct 2274 ms 31796 KB Output is correct
14 Correct 2623 ms 63280 KB Output is correct
15 Correct 3825 ms 39924 KB Output is correct
16 Correct 3543 ms 51060 KB Output is correct
17 Correct 3273 ms 94504 KB Output is correct