oj.uz

Submission #1019480

# Submission time Handle Problem Language Result Execution time Memory
1019480 2024-07-10T23:43:54 Z vjudge1 Regions (IOI09_regions) C++17
27 / 100
 6446 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 200100
#define SZ 410
#define R 25010
int CC,in[N],out[N],id[R],prc[SZ][SZ],hv[SZ],CC2,reg[N],ANS;
vector<int>hav[N],adj[N];
map<int,int> sup[R],sub[R];
void upd(map<int,int>&mp,int x,int v){
    while(x<N) mp[x]+=v,x+=x&-x;
}
void query(map<int,int>&mp,int x,int v){
    while(x) ANS+=mp[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;
    upd(sup[reg[n]],in[n],1);
    upd(sup[reg[n]],out[n]+1,-1);
    upd(sub[reg[n]],in[n],1);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,q;
    cin>>n>>q>>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[a][b];
        else if(hav[a].size()>hav[b].size())
            for(auto i:hav[b])
                query(sup[a],in[i],1);
        else for(auto i:hav[a])
            query(sub[b],in[i]-1,-1),
            query(sub[b],out[i],1);
        cout<<ANS<<endl;
    }
}

Subtask #1
12.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12120 KB Output is correct
2 Correct 5 ms 12120 KB Output is correct
3 Correct 5 ms 12156 KB Output is correct
4 Correct 9 ms 12200 KB Output is correct
5 Correct 12 ms 13144 KB Output is correct
6 Correct 18 ms 13400 KB Output is correct
7 Correct 39 ms 16208 KB Output is correct
8 Correct 44 ms 17168 KB Output is correct
9 Correct 95 ms 24460 KB Output is correct
10 Correct 251 ms 47440 KB Output is correct
11 Correct 695 ms 81056 KB Output is correct
12 Correct 711 ms 89364 KB Output is correct
13 Runtime error 1131 ms 131072 KB Execution killed with signal 9
14 Runtime error 1111 ms 131072 KB Execution killed with signal 9
15 Runtime error 832 ms 131072 KB Execution killed with signal 9

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 1449 ms 131072 KB Execution killed with signal 9
2 Runtime error 1344 ms 131072 KB Execution killed with signal 9
3 Runtime error 1002 ms 131072 KB Execution killed with signal 9
4 Correct 647 ms 75824 KB Output is correct
5 Correct 1048 ms 107400 KB Output is correct
6 Runtime error 191 ms 99268 KB Execution killed with signal 11
7 Correct 6446 ms 104148 KB Output is correct
8 Runtime error 802 ms 131072 KB Execution killed with signal 9
9 Runtime error 448 ms 131072 KB Execution killed with signal 9
10 Runtime error 495 ms 131072 KB Execution killed with signal 9
11 Runtime error 387 ms 131072 KB Execution killed with signal 9
12 Runtime error 421 ms 131072 KB Execution killed with signal 9
13 Runtime error 441 ms 131072 KB Execution killed with signal 9
14 Runtime error 476 ms 131072 KB Execution killed with signal 9
15 Runtime error 440 ms 131072 KB Execution killed with signal 9
16 Runtime error 393 ms 131072 KB Execution killed with signal 9
17 Runtime error 562 ms 131072 KB Execution killed with signal 9