oj.uz

Submission #1019485

# Submission time Handle Problem Language Result Execution time Memory
1019485 2024-07-10T23:58:44 Z vjudge1 Regions (IOI09_regions) C++17
90 / 100
 6041 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;
#include<bits/extc++.h>
using namespace __gnu_pbds;
#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];
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<SZ;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);
    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;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10072 KB Output is correct
2 Correct 5 ms 10072 KB Output is correct
3 Correct 6 ms 10072 KB Output is correct
4 Correct 7 ms 9980 KB Output is correct
5 Correct 8 ms 10324 KB Output is correct
6 Correct 13 ms 10072 KB Output is correct
7 Correct 19 ms 10072 KB Output is correct
8 Correct 27 ms 10072 KB Output is correct
9 Correct 45 ms 10584 KB Output is correct
10 Correct 71 ms 10584 KB Output is correct
11 Correct 124 ms 10840 KB Output is correct
12 Correct 117 ms 11352 KB Output is correct
13 Correct 186 ms 10840 KB Output is correct
14 Correct 333 ms 11352 KB Output is correct
15 Correct 385 ms 14680 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1988 ms 57296 KB Output is correct
2 Correct 2139 ms 57464 KB Output is correct
3 Correct 3283 ms 55568 KB Output is correct
4 Correct 332 ms 11528 KB Output is correct
5 Correct 337 ms 13656 KB Output is correct
6 Correct 1494 ms 20124 KB Output is correct
7 Correct 2310 ms 13656 KB Output is correct
8 Correct 2252 ms 25592 KB Output is correct
9 Correct 3234 ms 19172 KB Output is correct
10 Correct 6041 ms 24908 KB Output is correct
11 Correct 5606 ms 18592 KB Output is correct
12 Correct 1653 ms 48808 KB Output is correct
13 Correct 2329 ms 49444 KB Output is correct
14 Runtime error 1488 ms 131072 KB Execution killed with signal 9
15 Correct 3953 ms 54200 KB Output is correct
16 Correct 4062 ms 61276 KB Output is correct
17 Runtime error 2613 ms 131072 KB Execution killed with signal 9