Submission #53616

#TimeUsernameProblemLanguageResultExecution timeMemory
53616baactreeRegions (IOI09_regions)C++17
0 / 100
4403 ms94356 KiB
#include <bits/stdc++.h> using namespace std; int n, r, q; vector<int> adj[200005]; int arr[200005]; const int sz = 505; int dp[sz][25005]; pair<int,int> cnt[25005]; int inv[25005]; bitset<sz> bs[200005]; int le[200005], ri[200005]; vector<int> idx[25005]; vector<pair<int, int> > vec[25005]; int vn; void dfs(int now, int par) { if (inv[arr[now]] < sz)bs[now][inv[arr[now]]] = 1; bs[now] |= bs[par]; idx[arr[now]].push_back(vn); le[now] = vn++; for (auto &there : adj[now]) { if (there == par)continue; dfs(there, now); } ri[now] = vn++; if (inv[arr[now]] >= sz) vec[arr[now]].emplace_back(le[now], ri[now]); } int main() { scanf("%d%d%d", &n, &r, &q); scanf("%d", &arr[1]); cnt[arr[1]].first++; for (int i = 2; i <= n; i++) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(i); adj[i].push_back(a); arr[i] = b; cnt[arr[i]].first++; } for (int i = 0; i < 25005; i++) cnt[i].second = i; sort(cnt, cnt + 25005); reverse(cnt,cnt + 25005); for (int i = 0; i < 25005; i++) inv[cnt[i].second] = i; dfs(1, 0); for (int i = 1; i <= n; i++) { for (int j = 0; j < sz; j++) if (bs[i][j])dp[j][arr[i]]++; } for (int i = 0; i < 25005; i++) sort(vec[i].begin(), vec[i].end()); while (q--) { int a, b; scanf("%d%d", &a, &b); if (inv[a] < sz) { printf("%d\n", dp[inv[a]][b]); fflush(stdout); } else { int pre = -1; int ans = 0; for (auto x : vec[a]) { int le = x.first; int ri = x.second; if (le <= pre)continue; ans += upper_bound(idx[b].begin(), idx[b].end(), ri) - lower_bound(idx[b].begin(), idx[b].end(), le); pre = ri; } printf("%d\n", ans); fflush(stdout); } } return 0; }

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &r, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &arr[1]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...