Submission #686807

#	Time	Username	Problem	Language	Result	Execution time	Memory
686807		boyliguanhan	Regions (IOI09_regions)	C++17	18 / 100	1291 ms	131072 KiB

regions

#include<bits/stdc++.h>
using namespace std;
vector<int> adj[200100];
int region[200100];
int answers[501][501];
vector<int> regions[25100];
map<int, int> vals[200100];
void merge(map<int, int> &a, map<int, int> b){
    if(a.size()<b.size())
        swap(a, b);
    for(auto i: b)
        a[i.first]+=i.second;
}
void dfs(int n){
    regions[region[n]].push_back(n);
    vals[n][region[n]]=1;
    for(auto i: adj[n]){
        dfs(i);
        merge(vals[n], vals[i]);
    }
}
int main(){
    int n, r, q;
    cin >> n >> r >> q;
    cin >> region[0];
    for(int i = 1; i < n; i++){
        int p;
        cin >> p >> region[i];
        adj[p-1].push_back(i);
    }
    dfs(0);
    if(r<501){
        for(int i = 1; i <= r; i++){
            for(auto j : regions[i]){
                for(auto k: vals[j]){
                    answers[i][k.first]+=k.second;
                }
            }
        }
        while(q--){
            int a, b;
            cin >> a >> b;
            cout << answers[a][b] << endl;
        }
    } else {
        while(q--){
            int a, b, ans = 0;
            cin >> a >> b;
            for(auto i: regions[a])
                if(vals[i].count(b))
                    ans+=vals[i][b];
            cout << ans << endl;
        }
    }
    return 0;
}

• Subtask 1: 13 / 15
• Subtask 2: 5 / 85