Submission #526464

#	Time	Username	Problem	Language	Result	Execution time	Memory
526464		PiejanVDC	Regions (IOI09_regions)	C++17	19 / 100	8055 ms	131076 KiB

regions

#include <bits/stdc++.h>
using namespace std;

vector<int>top;
vector<int>adj[(int)2e5+5];
vector<int>region;

map<pair<int,int>,int>mp;

void dfs(int u, int e = -1) {
    for(auto z : top) {
        mp[{region[u],region[z]}]++;
    }
    top.push_back(u);
    for(auto z : adj[u]) if(z != e) {
        dfs(z,u);
    }
    top.pop_back();
}

signed main() {
    int n,r,q; cin>>n>>r>>q;
    region.resize(n);
    int h; cin>>h; region[0] = h;
    for(int i = 1 ; i < n ; i++) {
        int s,h; cin>>s>>h;
        s--;
        adj[s].push_back(i);
        region[i] = h;
    }
    dfs(0);
    while(q--) {
        int a,b; cin>>a>>b;
        cout << flush << mp[{b,a}] << "\n";
    }
    return 0;
}

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