oj.uz

Submission #1019492

# Submission time Handle Problem Language Result Execution time Memory
1019492 2024-07-11T00:19:02 Z boyliguanhan Regions (IOI09_regions) C++17
100 / 100
 7668 ms 67964 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define N 200100
#define SZ 410
int CC,in[N],out[N],id[N],prc[SZ][SZ],hv[SZ],CC2,reg[N],ANS,T[N];
vector<int>hav[N],adj[N];
gp_hash_table<int,int> sup[SZ],sub[SZ],sup2[SZ],sub2[SZ];
void upd(gp_hash_table<int,int>&mp,int x,int v){
    while(x<N)mp[x]+=v,x+=x&-x;
}
void query(gp_hash_table<int,int>&mp,int x,int v){
    while(x)ANS+=mp[x]*v,x-=x&-x;
}
void upd2(int x,int v){
    while(x<N) T[x]+=v,x+=x&-x;
}
void query2(int x,int v){
    while(x) ANS+=T[x]*v,x-=x&-x;
}
void dfs(int n){
    if(id[reg[n]])for(int i=1;i<=CC2;i++)
        prc[i][id[reg[n]]]+=hv[i];
    hv[id[reg[n]]]++; in[n]=++CC;
    for(auto i:adj[n])dfs(i);
    hv[id[reg[n]]]--; out[n]=CC;
    if(id[reg[n]])
        upd(sup[id[reg[n]]],in[n],1),
        upd(sup[id[reg[n]]],out[n]+1,-1),
        upd(sub[id[reg[n]]],in[n],1);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,q,r;
    cin>>n>>r>>q;
    cin>>reg[1];
    for(int i=2;i<=n;i++){
        int p;cin>>p>>reg[i];
        adj[p].push_back(i);
    }
    for(int i=1;i<=n;i++)
        hav[reg[i]].push_back(i);
    for(int i=1;i<=r;i++)
        if(hav[i].size()>=500)
            id[i]=++CC2;
    dfs(1);
    for(int i=1;i<=CC2;i++)
        sub2[i]=sub[i],sup2[i]=sup[i];
    while(q--){
        int a,b;
        cin>>a>>b;
        ANS=0;
        if(id[a]&&id[b])
            ANS=prc[id[a]][id[b]];
        else if(id[a]||id[b])
            if(hav[a].size()>hav[b].size())
                for(auto i:hav[b])
                    query(sup[id[a]],in[i],1);
            else for(auto i:hav[a])
                query(sub[id[b]],in[i]-1,-1),
                query(sub[id[b]],out[i],1);
        else {
            for(auto i:hav[a])
                upd2(in[i],1),
                upd2(out[i]+1,-1);
            for(auto i:hav[b])
                query2(in[i],1);
            for(auto i:hav[a])
                upd2(in[i],-1),
                upd2(out[i]+1,1);
        }
        cout<<ANS<<endl;
        if(q%500==0)for(int i=1;i<=CC2;i++)
            sub[i]=sub2[i],sup[i]=sup2[i];
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10072 KB Output is correct
2 Correct 3 ms 10072 KB Output is correct
3 Correct 4 ms 10072 KB Output is correct
4 Correct 6 ms 10208 KB Output is correct
5 Correct 9 ms 10156 KB Output is correct
6 Correct 10 ms 10328 KB Output is correct
7 Correct 23 ms 10332 KB Output is correct
8 Correct 26 ms 10328 KB Output is correct
9 Correct 34 ms 10840 KB Output is correct
10 Correct 59 ms 10584 KB Output is correct
11 Correct 116 ms 10844 KB Output is correct
12 Correct 134 ms 12120 KB Output is correct
13 Correct 181 ms 11096 KB Output is correct
14 Correct 307 ms 11608 KB Output is correct
15 Correct 390 ms 15348 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3004 ms 33708 KB Output is correct
2 Correct 3714 ms 38612 KB Output is correct
3 Correct 4686 ms 34776 KB Output is correct
4 Correct 321 ms 11608 KB Output is correct
5 Correct 346 ms 13656 KB Output is correct
6 Correct 1991 ms 23484 KB Output is correct
7 Correct 2224 ms 13912 KB Output is correct
8 Correct 2311 ms 21320 KB Output is correct
9 Correct 3349 ms 19328 KB Output is correct
10 Correct 6037 ms 25168 KB Output is correct
11 Correct 5380 ms 18756 KB Output is correct
12 Correct 1965 ms 35156 KB Output is correct
13 Correct 2898 ms 35604 KB Output is correct
14 Correct 5484 ms 55192 KB Output is correct
15 Correct 5047 ms 40280 KB Output is correct
16 Correct 5163 ms 47592 KB Output is correct
17 Correct 7668 ms 67964 KB Output is correct