Submission #909105

#	Time	Username	Problem	Language	Result	Execution time	Memory
909105		anarch_y	Regions (IOI09_regions)	C++17	45 / 100	8086 ms	23672 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 st[maxn], en[maxn];
int timer = 0;

void dfs(int s, int p){
    st[s] = timer++;
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
    }
    en[s] = timer;
}

bool anc(int a, int b){
    return st[a] <= st[b] and en[b] <= en[a];
}

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

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

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        int ans = 0;
        for(auto a: reg[r1]){
            for(auto b: reg[r2]){
                if(anc(a, b)) ans++;
            }
        }
        cout << ans << "\n";
        cout.flush();
    }
}

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