Submission #638135

#	Time	Username	Problem	Language	Result	Execution time	Memory
638135		Iwanttobreakfree	Regions (IOI09_regions)	C++17	18 / 100	985 ms	131072 KiB

regions

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int ans;
map<int,int> dfs(int a,vector<vector<int>>& g,vector<int>& reg,vector<map<int,int>>& ans){
    for(int u:g[a]){
        map<int,int> x=dfs(u,g,reg,ans);
        if(x.size()>ans[a].size())swap(x,ans[a]);
        for(auto y:x)ans[a][y.first]+=y.second;
        ans[a][reg[u]]++;
    }
    return ans[a];
}
int main(){
    int n,r,q,x,y;
    cin>>n>>r>>q;
    vector<int> reg(n);
    vector<vector<int>> g(n,vector<int>());
    vector<map<int,int>> ans(n,map<int,int>());
    vector<vector<int>> sol(r+1,vector<int>(r+1));
    cin>>reg[0];
    for(int i=1;i<n;i++){
        cin>>x>>reg[i];
        x--;
        g[x].push_back(i);
    }
    dfs(0,g,reg,ans);
    for(int i=0;i<n;i++){
        for(auto mp:ans[i]){
            //cout<<mp.first<<' ';
            sol[reg[i]][mp.first]+=mp.second;
        }
    }
    while(q--){
        cin>>x>>y;
        cout<<sol[x][y]<<'\n';
    }
}

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