oj.uz

Submission #1019487

# Submission time Handle Problem Language Result Execution time Memory
1019487 2024-07-11T00:01:43 Z vjudge1 Regions (IOI09_regions) C++17
45 / 100
 8000 ms 31824 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) if(mp.find(x)!=mp.end())
        mp[x]+=v,x+=x&-x;
}
void query(gp_hash_table<int,int>&mp,int x,int v){
    while(x)  if(mp.find(x)!=mp.end())
        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 4 ms 10072 KB Output is correct
2 Correct 4 ms 10072 KB Output is correct
3 Correct 5 ms 10072 KB Output is correct
4 Correct 6 ms 10072 KB Output is correct
5 Correct 8 ms 10324 KB Output is correct
6 Correct 15 ms 10072 KB Output is correct
7 Correct 22 ms 10072 KB Output is correct
8 Correct 24 ms 10072 KB Output is correct
9 Correct 33 ms 10584 KB Output is correct
10 Correct 66 ms 10580 KB Output is correct
11 Correct 112 ms 10840 KB Output is correct
12 Correct 123 ms 11352 KB Output is correct
13 Correct 185 ms 10840 KB Output is correct
14 Correct 312 ms 11604 KB Output is correct
15 Correct 383 ms 14680 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8016 ms 13656 KB Time limit exceeded
2 Execution timed out 8070 ms 12888 KB Time limit exceeded
3 Execution timed out 8047 ms 15192 KB Time limit exceeded
4 Correct 330 ms 11608 KB Output is correct
5 Correct 389 ms 13656 KB Output is correct
6 Execution timed out 8058 ms 12632 KB Time limit exceeded
7 Correct 2393 ms 13656 KB Output is correct
8 Execution timed out 8071 ms 15448 KB Time limit exceeded
9 Correct 3441 ms 19176 KB Output is correct
10 Correct 6070 ms 24912 KB Output is correct
11 Correct 5808 ms 18604 KB Output is correct
12 Execution timed out 8101 ms 18516 KB Time limit exceeded
13 Execution timed out 8042 ms 18060 KB Time limit exceeded
14 Execution timed out 8016 ms 18000 KB Time limit exceeded
15 Execution timed out 8057 ms 20560 KB Time limit exceeded
16 Execution timed out 8052 ms 31824 KB Time limit exceeded
17 Execution timed out 8026 ms 19084 KB Time limit exceeded