Submission #1259843

#TimeUsernameProblemLanguageResultExecution timeMemory
1259843tormentRegions (IOI09_regions)C++20
39 / 100
452 ms40144 KiB
#include <iostream> #include <vector> using namespace std; const int N = 2e5 + 5; const int R = 25005; const int B = 150; vector<int> g[N], reg[R]; int r12[B][R], r21[B][R], in[N], out[N], T = 0; void dfs(int node, int par){ in[node] = ++T; for(int &v : g[node]){ if(v == par)continue; dfs(v, node); } out[node] = T; } struct BIT{ vector<int>fen; int sz; BIT(int n){ sz = n; fen.resize(n + 1); } void Update(int pos, int val){ while(pos <= sz){ fen[pos] += val; pos += (pos & -pos); } } int Sum(int pos){ int s = 0; while(pos > 0){ s += fen[pos]; pos -= (pos & -pos); } return s; } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, r, q; cin >> n >> r >> q; for(int i = 1;i <= n;++i){ if(i != 1){ int p; cin >> p; g[p].push_back(i); g[i].push_back(p); } int h; cin >> h; reg[h].push_back(i); } dfs(1, 1); vector<int>S, s(n + 1, -1); for(int i = 1;i <= r;++i){ if(reg[i].size() > B){ s[i] = S.size(); S.push_back(i); } } for(int r1 = 0;r1 < (int)S.size();++r1){ vector<int>v(n + 2); for(int j : reg[S[r1]]){ v[in[j]]++; v[out[j] + 1]--; } for(int i = 1;i <= n;++i){ v[i] += v[i - 1]; } for(int r2 = 1;r2 <= r;++r2){ for(int j : reg[r2]){ r12[r1][r2] += v[in[j]]; } } } for(int r2 = 0;r2 < (int)S.size();++r2){ vector<int>v(n + 1); for(int j : reg[S[r2]]){ v[in[j]]++; } for(int i = 1;i <= n;++i){ v[i] += v[i - 1]; } for(int r1 = 1;r1 <= r;++r1){ for(int j : reg[r1]){ r21[r2][r1] += v[out[j]] - v[in[j] - 1]; } } } BIT tree(n); while(q--){ int r1, r2; cin >> r1 >> r2; if(s[r1] != -1){ cout << r12[s[r1]][r2] << endl; } else if(s[r2] != -1){ cout << r21[s[r2]][r1] << endl; } else{ int res = 0; for(int j : reg[r2]){ tree.Update(in[j], 1); } for(int j : reg[r1]){ res += tree.Sum(out[j]) - tree.Sum(in[j] - 1); } for(int j : reg[r2]){ tree.Update(in[j], -1); } cout << res << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...