Submission #1244244

#TimeUsernameProblemLanguageResultExecution timeMemory
1244244whtthRegions (IOI09_regions)C++20
85 / 100
8048 ms34288 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; using ll = long long; const int MAXN = 200000; int n, r, m; int st[MAXN+1], en[MAXN+1], timer = 0; int country[MAXN+1]; vector<int> tree[MAXN+1]; // Lưu pair (st, en) cho mỗi node; sẽ sort theo st vector<pair<int,int>> nodes_by_country[25001]; void dfs(int u) { st[u] = ++timer; for (int v : tree[u]) dfs(v); en[u] = timer; // sau khi có st[u] và en[u], lưu vào country nodes_by_country[country[u]].emplace_back(st[u], en[u]); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> r >> m; for (int i = 1; i <= n; i++) { if (i == 1) { cin >> country[1]; } else { int p; cin >> p >> country[i]; tree[p].push_back(i); } } dfs(1); // với mỗi quốc gia, sort các pair theo st for (int c = 1; c <= r; c++) { auto &vec = nodes_by_country[c]; sort(vec.begin(), vec.end(), [](auto &a, auto &b){ return a.first < b.first; }); } while (m--) { int A, B; cin >> A >> B; ll ans = 0; auto &VA = nodes_by_country[A]; auto &VB = nodes_by_country[B]; // tách riêng mảng st của B để binary search vector<int> stB; stB.reserve(VB.size()); for (auto &pr : VB) stB.push_back(pr.first); for (auto &pr : VA) { int st_u = pr.first, en_u = pr.second; // số v có st[v] >= st_u auto itL = lower_bound(stB.begin(), stB.end(), st_u); // số v có st[v] > en_u auto itR = upper_bound(stB.begin(), stB.end(), en_u); ans += (itR - itL); } cout << ans << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...