oj.uz

Submission #908965

# Submission time Handle Problem Language Result Execution time Memory
908965 2024-01-17T03:48:06 Z 089487 Regions (IOI09_regions) C++14
55 / 100
 5894 ms 99968 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=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 4 ms 13912 KB Output is correct
2 Correct 4 ms 13912 KB Output is correct
3 Correct 4 ms 13912 KB Output is correct
4 Correct 6 ms 13912 KB Output is correct
5 Correct 9 ms 13912 KB Output is correct
6 Correct 13 ms 13912 KB Output is correct
7 Correct 21 ms 13912 KB Output is correct
8 Correct 23 ms 13912 KB Output is correct
9 Correct 32 ms 14420 KB Output is correct
10 Correct 65 ms 14168 KB Output is correct
11 Correct 123 ms 14640 KB Output is correct
12 Correct 133 ms 15000 KB Output is correct
13 Correct 185 ms 14660 KB Output is correct
14 Correct 355 ms 15152 KB Output is correct
15 Correct 341 ms 16720 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1466 ms 39128 KB Output is correct
2 Correct 1639 ms 32868 KB Output is correct
3 Correct 3169 ms 42240 KB Output is correct
4 Correct 340 ms 15076 KB Output is correct
5 Correct 341 ms 16264 KB Output is correct
6 Correct 1256 ms 34864 KB Output is correct
7 Correct 2493 ms 16480 KB Output is correct
8 Correct 2274 ms 29620 KB Output is correct
9 Incorrect 3304 ms 20120 KB Output isn't correct
10 Incorrect 5792 ms 23932 KB Output isn't correct
11 Incorrect 5894 ms 19380 KB Output isn't correct
12 Incorrect 1640 ms 26600 KB Output isn't correct
13 Incorrect 2239 ms 29148 KB Output isn't correct
14 Incorrect 2543 ms 66956 KB Output isn't correct
15 Incorrect 4003 ms 34000 KB Output isn't correct
16 Incorrect 2790 ms 45140 KB Output isn't correct
17 Incorrect 2786 ms 99968 KB Output isn't correct