제출 #1043577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1043577		Azm1t	Regions (IOI09_regions)	C++17	0 / 100	8077 ms	36176 KiB

regions

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

#define rep(i, a, b) for (long long i = a; i < b; i++)
#define sz(x) static_cast<long long>((x).size())
#define all(x) (x).begin(), (x).end()

// #define int long long
#define double long double
const long long inf = (long long) 1e18;
const int mod = (int) 998244353;

signed main(){

    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout << fixed << setprecision(10);

    int n, r, q; cin >> n >> r >> q;
    vector<vector<int>> adj(n);

    vector<int> color[r];
    vector<int> region(n);
    vector<int> regiontotime[r];
    cin >> region[0]; region[0]--;
    color[region[0]].push_back(0);

    rep(i, 1, n){
        int y; cin >> y >> region[i];
        y--; region[i]--;
        adj[y].push_back(i);
        color[region[i]].push_back(i);
    }

    vector<int> pc;
    rep(i, 0, r) if(sz(color[i])*sz(color[i]) >= n) pc.push_back(i);

    map<pair<int, int>, int> precomp;
    vector<int> in(n, 0), out(n, 0), szz(n, 1);
    int time = 0;

    function<void(int, int)> dfs = [&](int v, int p){
        in[v] = time++;
        regiontotime[region[v]].push_back(in[v]);
        for(auto child: adj[v]){
            dfs(child, v);
            szz[v] += szz[child];
        }
        out[v] = time++;
    };

    dfs(0, -1);

    for(auto u: pc){
        for(auto v: pc){
            if(u == v) continue;
            for(auto val: color[u]){
                precomp[{u, v}] += upper_bound(all(regiontotime[region[v]]), out[val]) - lower_bound(all(regiontotime[region[v]]), in[val]);
            }
        }
    }

    while(q--){
        int u, v; cin >> u >> v; u--; v--;
        if(precomp.find({u, v}) != precomp.end()) cout << precomp[{u, v}] << endl;
        else{
            int res = 0;
            for(auto val: color[u]) res += upper_bound(all(regiontotime[region[v]]), out[val]) - lower_bound(all(regiontotime[region[v]]), in[val]);
            cout << res << endl;
        }
    }

    
}	

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