Submission #556320

#TimeUsernameProblemLanguageResultExecution timeMemory
556320GioChkhaidzeRegions (IOI09_regions)C++14
100 / 100
3107 ms104452 KiB
#include <bits/stdc++.h> #define pb push_back #define f first #define s second using namespace std; const int N = 2e5 + 5; const int M = 25005; int sq; bool Hv[M], Lh[M]; int n, r, q, timer; vector < int > s, v[N], R[M]; int in[N], out[N], O[N], c[N], p[N], idx[M], G[M][800], cur[800]; bool is_anc(int a, int b) { return (in[a] <= in[b] && out[b] <= out[a]); } void dfs(int x) { in[x] = ++timer; O[timer] = x; for (int i = 0; i < v[x].size(); ++i) { int to = v[x][i]; dfs(to); } out[x] = timer; } void wfs(int x) { int col = c[x]; for (int i = 0; i < s.size(); ++i) { if (col == s[i]) continue; G[col][i] += cur[i]; } if (Hv[col]) { ++cur[idx[col]]; } for (int i = 0; i < v[x].size(); ++i) { int to = v[x][i]; wfs(to); } if (Hv[col]) { --cur[idx[col]]; } } main () { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> r >> q; cin >> c[1]; for (int i = 2; i <= n; ++i) { cin >> p[i] >> c[i]; v[p[i]].pb(i); } dfs(1); for (int i = 1; i <= n; ++i) { R[c[i]].pb(in[i]); } sq = 200; for (int i = 1; i <= r; ++i) { sort(R[i].begin(), R[i].end()); if (R[i].size() > sq) { idx[i] = s.size(); Hv[i] = true; s.pb(i); } else { Lh[i] = true; } } wfs(1); for (int i = 1; i <= q; ++i) { int x, y, ans = 0; cin >> x >> y; if (Lh[x]) { for (int j = 0; j < R[x].size(); ++j) { int id = O[R[x][j]]; int Rc = (lower_bound(R[y].begin(), R[y].end(), out[id] + 1) - R[y].begin()); int Lc = (lower_bound(R[y].begin(), R[y].end(), in[id]) - R[y].begin()); ans += Rc - Lc; } } else { ans = G[y][idx[x]]; } cout << ans << endl; } }

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'void wfs(int)':
regions.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~
regions.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main () {
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:71:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |   if (R[i].size() > sq) {
      |       ~~~~~~~~~~~~^~~~
regions.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for (int j = 0; j < R[x].size(); ++j) {
      |                    ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...