oj.uz

Submission #908967

# Submission time Handle Problem Language Result Execution time Memory
908967 2024-01-17T03:50:26 Z 089487 Regions (IOI09_regions) C++14
90 / 100
 6130 ms 131072 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4,abm,avx,popcnt")
#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=450;
const int K2=450;
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:25:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   25 | const int INF=1e18;
      |               ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 26200 KB Output is correct
2 Correct 8 ms 26200 KB Output is correct
3 Correct 10 ms 26044 KB Output is correct
4 Correct 10 ms 26200 KB Output is correct
5 Correct 12 ms 26200 KB Output is correct
6 Correct 15 ms 26200 KB Output is correct
7 Correct 21 ms 26200 KB Output is correct
8 Correct 26 ms 26200 KB Output is correct
9 Correct 37 ms 26456 KB Output is correct
10 Correct 71 ms 26456 KB Output is correct
11 Correct 124 ms 26872 KB Output is correct
12 Correct 133 ms 27228 KB Output is correct
13 Correct 204 ms 26888 KB Output is correct
14 Correct 373 ms 27388 KB Output is correct
15 Correct 361 ms 28772 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1360 ms 73292 KB Output is correct
2 Correct 1610 ms 53240 KB Output is correct
3 Correct 3139 ms 61044 KB Output is correct
4 Correct 321 ms 27308 KB Output is correct
5 Correct 353 ms 28616 KB Output is correct
6 Correct 435 ms 83460 KB Output is correct
7 Correct 1982 ms 42656 KB Output is correct
8 Runtime error 98 ms 131072 KB Execution killed with signal 9
9 Correct 3500 ms 34844 KB Output is correct
10 Runtime error 170 ms 131072 KB Execution killed with signal 9
11 Correct 6130 ms 33852 KB Output is correct
12 Correct 1424 ms 44724 KB Output is correct
13 Correct 2089 ms 44288 KB Output is correct
14 Correct 2271 ms 80644 KB Output is correct
15 Correct 3712 ms 45992 KB Output is correct
16 Correct 3474 ms 49596 KB Output is correct
17 Correct 3119 ms 124924 KB Output is correct