oj.uz

Submission #908968

# Submission time Handle Problem Language Result Execution time Memory
908968 2024-01-17T03:52:30 Z 089487 Regions (IOI09_regions) C++14
85 / 100
 6192 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=400;
const int K2=500;
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 8 ms 24664 KB Output is correct
2 Correct 7 ms 24704 KB Output is correct
3 Correct 8 ms 24664 KB Output is correct
4 Correct 8 ms 24664 KB Output is correct
5 Correct 12 ms 24664 KB Output is correct
6 Correct 15 ms 24664 KB Output is correct
7 Correct 29 ms 24664 KB Output is correct
8 Correct 38 ms 24664 KB Output is correct
9 Correct 37 ms 24920 KB Output is correct
10 Correct 65 ms 25176 KB Output is correct
11 Correct 129 ms 25416 KB Output is correct
12 Correct 127 ms 25988 KB Output is correct
13 Correct 197 ms 25432 KB Output is correct
14 Correct 376 ms 25928 KB Output is correct
15 Correct 348 ms 27416 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1367 ms 85304 KB Output is correct
2 Correct 1702 ms 51816 KB Output is correct
3 Correct 3256 ms 57432 KB Output is correct
4 Correct 343 ms 25852 KB Output is correct
5 Correct 341 ms 26956 KB Output is correct
6 Correct 385 ms 92412 KB Output is correct
7 Correct 1448 ms 54488 KB Output is correct
8 Runtime error 144 ms 131072 KB Execution killed with signal 9
9 Correct 3713 ms 33452 KB Output is correct
10 Runtime error 198 ms 131072 KB Execution killed with signal 9
11 Correct 6192 ms 32208 KB Output is correct
12 Correct 1465 ms 41048 KB Output is correct
13 Correct 2187 ms 41976 KB Output is correct
14 Correct 2359 ms 85928 KB Output is correct
15 Correct 3862 ms 46832 KB Output is correct
16 Correct 3451 ms 58212 KB Output is correct
17 Runtime error 235 ms 131072 KB Execution killed with signal 9