oj.uz

Submission #908964

# Submission time Handle Problem Language Result Execution time Memory
908964 2024-01-17T03:44:57 Z 089487 Regions (IOI09_regions) C++14
50 / 100
 5470 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;
}
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 4 ms 14168 KB Output is correct
2 Correct 4 ms 14168 KB Output is correct
3 Correct 4 ms 14168 KB Output is correct
4 Correct 6 ms 14168 KB Output is correct
5 Correct 8 ms 14168 KB Output is correct
6 Correct 12 ms 14168 KB Output is correct
7 Correct 17 ms 14168 KB Output is correct
8 Correct 24 ms 14168 KB Output is correct
9 Correct 36 ms 14420 KB Output is correct
10 Correct 66 ms 14680 KB Output is correct
11 Correct 113 ms 14948 KB Output is correct
12 Correct 129 ms 15320 KB Output is correct
13 Correct 203 ms 15216 KB Output is correct
14 Correct 376 ms 15460 KB Output is correct
15 Correct 342 ms 16984 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1382 ms 51672 KB Output is correct
2 Correct 1587 ms 32952 KB Output is correct
3 Correct 3148 ms 42472 KB Output is correct
4 Correct 329 ms 15404 KB Output is correct
5 Correct 319 ms 16860 KB Output is correct
6 Correct 413 ms 68064 KB Output is correct
7 Correct 1979 ms 28212 KB Output is correct
8 Runtime error 165 ms 131072 KB Execution killed with signal 9
9 Incorrect 3351 ms 20420 KB Output isn't correct
10 Runtime error 257 ms 131072 KB Execution killed with signal 9
11 Incorrect 5470 ms 19680 KB Output isn't correct
12 Incorrect 1359 ms 27052 KB Output isn't correct
13 Incorrect 1916 ms 29452 KB Output isn't correct
14 Incorrect 2292 ms 65984 KB Output isn't correct
15 Incorrect 3503 ms 34304 KB Output isn't correct
16 Incorrect 2560 ms 45436 KB Output isn't correct
17 Incorrect 2597 ms 99628 KB Output isn't correct