Submission #1100318

#TimeUsernameProblemLanguageResultExecution timeMemory
1100318Muaath_5Regions (IOI09_regions)C++17
90 / 100
8016 ms76872 KiB
// Problem: D - Regions // Contest: Virtual Judge - 2024-10-13 - 10/10 problems // URL: https://vjudge.net/contest/661996#problem/D // Memory Limit: 128 MB // Time Limit: 8000 ms // // By Muaath Alqarni // Blog: https://muaath5.githib.io/blog // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> #define ll long long #define pii pair<int, int> using namespace std; const int N = 2e5+1, R = 25001, SQ = 500; int n, r, q, reg[N]; vector<int> adj[N]; vector<int> people[R]; // dfs tree int ttt = 1, dt[N], ft[N]; void dfs(int node) { dt[node] = ttt++; for (int ch : adj[node]) { dfs(ch); } ft[node] = ttt-1; } // small & big int type[R]; // boolean 0=small, 1=big int idx[R]; int big_any[SQ][R]; int any_big[R][SQ]; int srch = 0; int sum[N]; void dfs2(int node) { sum[node] = (reg[node] == srch); for (int ch : adj[node]) { dfs2(ch); sum[node] += sum[ch]; } } int fakelazy[N] = {}; int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n >> r >> q; for (int i = 1; i <= n; i++) { if (i != 1) { int p; cin >> p; adj[p].push_back(i); } cin >> reg[i]; people[reg[i]].push_back(i); } dfs(1); // precalc int lstidx = 0; for (int i = 1; i <= r; i++) { type[i] = (people[i].size() >= SQ); if (type[i]) { idx[i] = lstidx++; memset(fakelazy, 0, sizeof(fakelazy)); // precalculate // big_any for (int c : people[i]) { fakelazy[dt[c]]++; fakelazy[ft[c]+1]--; } for (int j = 1; j <= n; j++) fakelazy[j] += fakelazy[j-1]; for (int j = 1; j <= n; j++) big_any[idx[i]][reg[j]] += fakelazy[dt[j]]; // any_big srch = i; dfs2(1); for (int j = 1; j <= n; j++) any_big[reg[j]][idx[i]] += sum[j]; } } while (q--) { int r1, r2; cin >> r1 >> r2; if (type[r1]) cout #ifdef MUAATH_5 << '#' #endif << big_any[idx[r1]][r2] << endl; else if (type[r2]) cout #ifdef MUAATH_5 << '*' #endif << any_big[r1][idx[r2]] << endl; else { int sol = 0; for (int c1 : people[r1]) { for (int c2 : people[r2]) { if (dt[c1] <= dt[c2] && dt[c2] <= ft[c1]) sol++; } } cout << sol << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...