Submission #1203597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203597		Hamed_Ghaffari	Regions (IOI09_regions)	C++20	100 / 100	2609 ms	37576 KiB

regions

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

using pii = pair<int, int>;

const int MXN = 2e5+5, MXR = 25e3+4, sq = 400, sqi = MXN/sq+5;

int n, R, q, H[MXN], stt[MXN], fnt[MXN], timer;
vector<int> g[MXN], pos[MXR], posv[MXR];
int posbig[MXR];
vector<pii> vec[MXR];
int dp[sqi][sqi];

void dfs(int v) {
    vec[H[v]].push_back(pii(stt[v]=timer++, vec[H[v]].empty() ? 1 : vec[H[v]].back().second+1));
    pos[H[v]].push_back(stt[v]);
    posv[H[v]].push_back(v);
    for(int u : g[v]) dfs(u);
    vec[H[v]].push_back(pii(fnt[v]=timer++, vec[H[v]].empty() ? -1 : vec[H[v]].back().second-1));
}

int dfs2(int v, int r) {
    int sz = H[v]==r;
    for(int u : g[v]) sz += dfs2(u, r);
    if(H[v]!=r && pos[H[v]].size()>=sq) dp[posbig[H[v]]][posbig[r]] += sz;
    return sz;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> R >> q;
    cin >> H[1];
    for(int i=2, p; i<=n; i++) {
        cin >> p >> H[i];
        g[p].push_back(i);
    }
    dfs(1);
    timer = 0;
    for(int i=1; i<=R; i++)
        if(pos[i].size()>=sq)
            posbig[i] = timer++;
    for(int i=1; i<=R; i++)
        if(pos[i].size()>=sq)
            dfs2(1, i);
    while(q--) {
        int r1, r2;
        cin >> r1 >> r2;
        if(pos[r1].size()<sq) {
            int ans = 0;
            for(int v : posv[r1])
                ans += lower_bound(pos[r2].begin(), pos[r2].end(), fnt[v])
                - lower_bound(pos[r2].begin(), pos[r2].end(), stt[v]);
            cout << ans << endl;
        }
        else if(pos[r2].size()<sq) {
            int ans = 0;
            for(int v : posv[r2]) {
                int ps = lower_bound(vec[r1].begin(), vec[r1].end(), pii(stt[v]+1, 0))-vec[r1].begin();
                if(ps>0) ans += vec[r1][ps-1].second;
            }
            cout << ans << endl;
        }
        else cout << dp[posbig[r1]][posbig[r2]] << endl;
    }
}

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