oj.uz

Submission #1019483

# Submission time Handle Problem Language Result Execution time Memory
1019483 2024-07-10T23:50:40 Z vjudge1 Regions (IOI09_regions) C++17
32 / 100
 6154 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[id[a]][id[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 3 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct
4 Correct 6 ms 13144 KB Output is correct
5 Correct 9 ms 13656 KB Output is correct
6 Correct 11 ms 14088 KB Output is correct
7 Correct 37 ms 16936 KB Output is correct
8 Correct 53 ms 17744 KB Output is correct
9 Correct 81 ms 25164 KB Output is correct
10 Correct 245 ms 48180 KB Output is correct
11 Correct 632 ms 82092 KB Output is correct
12 Correct 630 ms 90588 KB Output is correct
13 Runtime error 1006 ms 131072 KB Execution killed with signal 9
14 Runtime error 1065 ms 131072 KB Execution killed with signal 9
15 Runtime error 775 ms 131072 KB Execution killed with signal 9

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 1269 ms 131072 KB Execution killed with signal 9
2 Runtime error 1199 ms 131072 KB Execution killed with signal 9
3 Runtime error 878 ms 131072 KB Execution killed with signal 9
4 Correct 616 ms 76500 KB Output is correct
5 Correct 1040 ms 108088 KB Output is correct
6 Correct 6009 ms 78860 KB Output is correct
7 Correct 6154 ms 104616 KB Output is correct
8 Runtime error 841 ms 131072 KB Execution killed with signal 9
9 Runtime error 408 ms 131072 KB Execution killed with signal 9
10 Runtime error 442 ms 131072 KB Execution killed with signal 9
11 Runtime error 392 ms 131072 KB Execution killed with signal 9
12 Runtime error 426 ms 131072 KB Execution killed with signal 9
13 Runtime error 433 ms 131072 KB Execution killed with signal 9
14 Runtime error 458 ms 131072 KB Execution killed with signal 9
15 Runtime error 405 ms 131072 KB Execution killed with signal 9
16 Runtime error 370 ms 131072 KB Execution killed with signal 9
17 Runtime error 490 ms 131072 KB Execution killed with signal 9