Submission #840606

#TimeUsernameProblemLanguageResultExecution timeMemory
840606mat_jurRegions (IOI09_regions)C++17
21 / 100
1491 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;} auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";} #define debug(X) cerr << "["#X"]: " << X << '\n'; #else #define debug(X) ; #endif #define ll long long #define all(v) (v).begin(), (v).end() #define FOR(i,l,r) for(int i=(l);i<=(r);++i) #define ROF(i,r,l) for(int i=(r);i>=(l);--i) #define REP(i,n) FOR(i,0,(n)-1) #define ssize(x) int(x.size()) #define fi first #define se second #define eb emplace_back int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, r, q; cin >> n >> r >> q; vector<int> h(n); vector G(n, vector(0, 0)), wyst(r, vector(0, 0)); cin >> h[0]; h[0]--; FOR(i, 1, n-1) { int p; cin >> p >> h[i]; p--; h[i]--; G[p].eb(i); G[i].eb(p); } const int B = (int(sqrt(r))); vector<int> big, bigIdx(n, -1); vector<int> start(n), end(n), s(n); int timer = 0; function<void(int, int)> dfs2 = [&](int v, int p) { start[v] = timer++; s[v] = 1; for(auto w : G[v]) { if (w == p) continue; dfs2(w, v); s[v] += s[w]; } end[v] = timer-1; }; dfs2(0, -1); REP(i, n) wyst[h[i]].eb(start[i]); REP(i, r) { if (ssize(wyst[i]) > B) {big.eb(i); bigIdx[i] = ssize(big)-1;} } auto merge = [&](vector<int> &a, vector<int> &b) { REP(i, ssize(big)) a[i] += b[i]; return; }; vector ans(r, vector(ssize(big), 0ll)); function<vector<int>(int, int)> dfs = [&](int v, int p) { vector<int> cnt(ssize(big)); for(auto w : G[v]) { if (w == p) continue; vector<int> b = dfs(w, v); merge(cnt, b); } REP(i, ssize(big)) ans[h[v]][i] += cnt[i]; if(bigIdx[h[v]] >= 0) cnt[bigIdx[h[v]]]++; return cnt; }; dfs(0, -1); REP(j, q) { int r1, r2; cin >> r1 >> r2; r1--; r2--; if (bigIdx[r2] >= 0) { // cerr << "CASE 1 \n"; cout << ans[r1][bigIdx[r2]] << '\n'; cout.flush(); continue; } ll res = 0; for (auto v : wyst[r2]) { auto up = upper_bound(all(wyst[r1]), end[v])-1, low = lower_bound(all(wyst[r1]), start[v]); res += up-low+1; } cout << res << '\n'; cout.flush(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...