제출 #908479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
908479		anarch_y	Regions (IOI09_regions)	C++17	30 / 100	2281 ms	131072 KiB

regions

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

const int maxn = 200001;
vector<int> adj[maxn];
int home[maxn];
map<int, int> mp[maxn];
map<pair<int, int>, int> ans;

void dfs(int s, int p){
    mp[s][home[s]] = 1;
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        if(sz(mp[s]) < sz(mp[u])) swap(mp[u], mp[s]);
        for(auto &[r, m]: mp[u]) mp[s][r] += m; 
    }
    for(auto &[r, m]: mp[s]){
        if(r == home[s]){
            ans[{r, r}] += m-1;
        }
        else{
            ans[{home[s], r}] += m;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, R, Q; cin >> N >> R >> Q;
    int h; cin >> h; home[1] = h;
    for(int i=2; i<=N; i++){
        int p, g; cin >> p >> g;
        adj[i].pb(p); adj[p].pb(i);
        home[i] = g; 
    }
    dfs(1, 0);

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        cout << ans[{r1, r2}] << "\n";
        cout.flush();
    }
}

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