제출 #447174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447174		SirCovidThe19th	Regions (IOI09_regions)	C++14	100 / 100	4588 ms	49128 KiB

regions

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

#define lb(x, v) lower_bound(x.begin(), x.end(), v)

const int mN = 2e5+5, mR = 25005;

int n, r, q, R[mN], tin[mN], tout[mN], ti = 0, cntReg[mR]; 
vector<int> adj[mN], reg[mR], pos[mR]; vector<pair<int, int>> trav[mR]; 
map<pair<int, int>, int> store;

void dfs(int i){
    cntReg[R[i]]++; pos[R[i]].push_back(tin[i] = ti++);
    trav[R[i]].push_back({tin[i], cntReg[R[i]]});
    for (int x : adj[i]) dfs(x);
    trav[R[i]].push_back({ti, cntReg[R[i]]-1});
    cntReg[R[i]]--; tout[i] = ti-1; 
}

int main(){
    cin >> n >> r >> q; 
    for (int i = 1; i <= n; i++){
        if (i == 1) cin >> R[i];
        else{ int p; cin >> p >> R[i]; adj[p].push_back(i); }
        reg[R[i]].push_back(i);
    }dfs(1);
    while (q--){
        int a, b, ans = 0; bool swp = 0; cin >> a >> b;
        if (store.count({a, b})){ cout<<store[{a, b}]<<endl; continue; }
        if (reg[a].size() > reg[b].size()) swap(a, b), swp = 1;
        for (int x : reg[a]){
            if (swp){
                auto it = lb(trav[b], make_pair(tin[x], INT_MAX));
                if (it != trav[b].begin()) ans += prev(it)->second;
            }else ans += lb(pos[b], tout[x]+1)-lb(pos[b], tin[x]);
        }if (swp){ swap(a, b); } store[{a, b}] = ans; cout<<ans<<endl;
    }
}
 

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