oj.uz

Submission #1019491

# Submission time Handle Problem Language Result Execution time Memory
1019491 2024-07-11T00:13:17 Z vjudge1 Regions (IOI09_regions) C++17
100 / 100
 7185 ms 68264 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 10328 KB Output is correct
2 Correct 3 ms 10072 KB Output is correct
3 Correct 7 ms 10072 KB Output is correct
4 Correct 7 ms 10072 KB Output is correct
5 Correct 7 ms 10072 KB Output is correct
6 Correct 12 ms 10328 KB Output is correct
7 Correct 18 ms 10328 KB Output is correct
8 Correct 22 ms 10328 KB Output is correct
9 Correct 35 ms 10840 KB Output is correct
10 Correct 65 ms 10584 KB Output is correct
11 Correct 125 ms 10840 KB Output is correct
12 Correct 130 ms 11608 KB Output is correct
13 Correct 185 ms 11096 KB Output is correct
14 Correct 324 ms 11608 KB Output is correct
15 Correct 386 ms 14680 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2904 ms 33904 KB Output is correct
2 Correct 3649 ms 38860 KB Output is correct
3 Correct 4565 ms 34868 KB Output is correct
4 Correct 319 ms 12376 KB Output is correct
5 Correct 368 ms 13656 KB Output is correct
6 Correct 1971 ms 23512 KB Output is correct
7 Correct 2296 ms 14012 KB Output is correct
8 Correct 2271 ms 21328 KB Output is correct
9 Correct 3328 ms 19332 KB Output is correct
10 Correct 6149 ms 25184 KB Output is correct
11 Correct 5631 ms 18756 KB Output is correct
12 Correct 2184 ms 35164 KB Output is correct
13 Correct 3063 ms 35596 KB Output is correct
14 Correct 5756 ms 55220 KB Output is correct
15 Correct 5196 ms 40276 KB Output is correct
16 Correct 5315 ms 47580 KB Output is correct
17 Correct 7185 ms 68264 KB Output is correct