Submission #1254842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254842		mngoc._.	Regions (IOI09_regions)	C++20	100 / 100	2317 ms	48676 KiB

regions

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

const int maxn = 2e5 + 5;
const int maxr = 25005;
const int B = 500;
int n, r, q;
int h[maxn];
vector<int> heavy;
vector<int> regions[maxn];
vector<pair<int, int>> t[maxn];
vector<int> g[maxn];
int timer, tin[maxn], tout[maxn];
int calc[B + 5][maxr];
int calc_child[B + 5][maxr];
int id[maxr], depth[maxn];
int sz[maxn];
int et[maxn * 2];

void dfs(int u) {
    tin[u] = ++timer;
    et[timer] = u;
    for(auto v:g[u]) {
        dfs(v);
    }
    tout[u] = ++timer;
    et[timer] = u;
}
void dfs_build(int u, int color) {
    if(h[u] == color) ++depth[u];
    sz[u] = (h[u] == color);
    for(auto v:g[u]) {
        depth[v] = depth[u];
        dfs_build(v, color);
        sz[u] += sz[v];
    }
}
void solve() {
    cin >> n >> r >> q;
    cin >> h[1];
    for(int i = 2; i <= n; ++i) {
        int p; cin >> p >> h[i];
        g[p].push_back(i);
    }    
    dfs(1);
    for(int i = 1; i <= n; ++i) {
        regions[h[i]].push_back(i);
    }
    heavy.push_back(0);
    for(int i = 1; i <= r; ++i) {
        if((int)regions[i].size() > B) {
            id[i] = (int)heavy.size();
            heavy.push_back(i);
        }   
        for(auto u:regions[i]) {
            t[i].push_back({tin[u], 1});
            t[i].push_back({tout[u], -1});
        }
        sort(t[i].begin(), t[i].end());
    }
    for(int i = 1; i < (int)heavy.size(); ++i) {
        int u = heavy[i];
        for(int j = 1; j <= n; ++j) depth[j] = sz[j] = 0;
        dfs_build(1, u);
        for(int j = 1; j <= r; ++j) {
            if(u == j) continue;
            for(auto vertex:regions[j]) {
                calc[i][j] += depth[vertex];
                calc_child[i][j] += sz[vertex];
            }
        }
    }
    vector<pair<int ,int>> cur;
    while(q--) {
        int x, y; cin >> x >> y;
        if(id[x]) {
            cout << calc[id[x]][y] << endl;
        }
        else {
            if(id[y]) {
                cout << calc_child[id[y]][x] << endl;
            }
            else {
                cur.resize((int)t[x].size() + (int)t[y].size());
                merge(t[x].begin(), t[x].end(),
                t[y].begin(), t[y].end(), cur.begin());
                
                int res = 0, sum = 0;
                for(auto i:cur) {
                    if(h[et[i.first]] == y) {
                        if(i.second == 1) res += sum;
                    }
                    else {
                        sum += i.second;
                    }
                }
                cout << res << endl;
            }
        }
    }
    
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

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