oj.uz

Submission #647348

# Submission time Handle Problem Language Result Execution time Memory
647348 2022-10-02T09:27:54 Z Karuk Regions (IOI09_regions) C++14
100 / 100
 4999 ms 106688 KB 
#include<bits/stdc++.h>
using namespace std;
const int bucket=450;
int parent[200001];
vector<int>children[200001];
int reg[200001];///regions
vector<int>indexx[25001];
vector<int>regions[25001];
int ticker=0;
int beg[200001],en[200001];
void dfs(int n) {
    indexx[reg[n]].push_back(ticker);
    beg[n]=ticker++;
    for(int i:children[n]) {
        dfs(i);
    }
    en[n]=ticker-1;
}
vector<int>large;
int num[25001];
map<pair<int,int>,int>ans;
void dfs1(int n) {
    for(int i:large) {
        ans[{i,reg[n]}]+=num[i];
    }
    num[reg[n]]++;
    for(int i:children[n]) {
        dfs1(i);
    }
    num[reg[n]]--;

}
int main() {
    int n,r,q;cin>>n>>r>>q;
    cin>>reg[1];
    regions[reg[1]].push_back(1);
    for(int i=2;i<=n;i++) {
        cin>>parent[i]>>reg[i];
        children[parent[i]].push_back(i);
        regions[reg[i]].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=r;i++) {
        if(indexx[i].size()>=bucket)large.push_back(i);
    }
    dfs1(1);
    for(int i=0;i<q;i++) {
        int x,y;cin>>x>>y;
        if(indexx[x].size()>=bucket)cout<<ans[{x,y}]<<endl;
        else {
            int anss=0;
            for(int ind:regions[x]) {
                int pos1=upper_bound(indexx[y].begin(),indexx[y].end(),beg[ind])-indexx[y].begin();
                int pos2=upper_bound(indexx[y].begin(),indexx[y].end(),en[ind])-indexx[y].begin();
                anss+=pos2-pos1;

            }
            cout<<anss<<endl;
        }
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6096 KB Output is correct
2 Correct 3 ms 6096 KB Output is correct
3 Correct 6 ms 6096 KB Output is correct
4 Correct 8 ms 6096 KB Output is correct
5 Correct 12 ms 6224 KB Output is correct
6 Correct 19 ms 6224 KB Output is correct
7 Correct 35 ms 6224 KB Output is correct
8 Correct 36 ms 6224 KB Output is correct
9 Correct 43 ms 6992 KB Output is correct
10 Correct 86 ms 6736 KB Output is correct
11 Correct 132 ms 7120 KB Output is correct
12 Correct 152 ms 7888 KB Output is correct
13 Correct 127 ms 7248 KB Output is correct
14 Correct 307 ms 7888 KB Output is correct
15 Correct 285 ms 12880 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1736 ms 12112 KB Output is correct
2 Correct 2244 ms 10312 KB Output is correct
3 Correct 3015 ms 15328 KB Output is correct
4 Correct 330 ms 8008 KB Output is correct
5 Correct 437 ms 11168 KB Output is correct
6 Correct 884 ms 32724 KB Output is correct
7 Correct 1769 ms 19492 KB Output is correct
8 Correct 2159 ms 82432 KB Output is correct
9 Correct 1996 ms 17432 KB Output is correct
10 Correct 4999 ms 106688 KB Output is correct
11 Correct 4017 ms 16484 KB Output is correct
12 Correct 1556 ms 19572 KB Output is correct
13 Correct 2360 ms 20776 KB Output is correct
14 Correct 2995 ms 41652 KB Output is correct
15 Correct 3213 ms 29488 KB Output is correct
16 Correct 2722 ms 42436 KB Output is correct
17 Correct 3591 ms 61640 KB Output is correct