Submission #814371

#	Time	Username	Problem	Language	Result	Execution time	Memory
814371		qthang2k11	Regions (IOI09_regions)	C++17	100 / 100	3338 ms	128508 KiB

regions

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int mod = 1e9 + 7, N = 2e5 + 16, R = 2.5e4 + 16, inf = 1e9 + 16;
unordered_map<int, int, custom_hash> ans[R];
int tin[N], fin[N], node[N];
vector<int> re[R], adj[N];
int a[N], s[N];
bool vs[R];
 
int timer = 0;
void dfs(int x, int p) {
   tin[x] = ++timer;
   node[timer] = x;
   for (int y: adj[x])
      if (y != p)
         dfs(y, x);
   fin[x] = timer;
}
 
int32_t main() {
   int n, r, q; scanf("%d%d%d%d", &n, &r, &q, &a[1]);
   for (int i = 2; i <= n; i++) {
      int x; scanf("%d%d", &x, &a[i]);
      adj[x].push_back(i);
      adj[i].push_back(x);
   }
   dfs(1, 1);
   for (int i = 1; i <= n; i++)
      re[a[node[i]]].push_back(i);
   int sq = sqrt(n);
   for (int i = 1; i <= n; i++) {
      int x = node[i], r = a[x];
      if (vs[r] || (int)re[r].size() <= sq) continue;
      for (int i = 1; i <= n; i++) s[i] = 0;
      for (int l: re[r]) {
         int r = fin[node[l]];
         ++s[l]; --s[r + 1];
      }
      for (int i = 1; i <= n; i++) { 
         s[i] += s[i - 1];
         ans[r][a[node[i]]] += s[i];
      }
      vs[r] = 1;
   }
   for (int tt = 1; tt <= q; tt++) {
      int r1, r2; scanf("%d%d", &r1, &r2);
      int kq = 0;
      if ((int)re[r1].size() > sq) kq = ans[r1][r2];
      else {
         for (int l: re[r1]) {
            int r = fin[node[l]];
            int x = upper_bound(re[r2].begin(), re[r2].end(), l) - re[r2].begin();
            int y = upper_bound(re[r2].begin(), re[r2].end(), r) - re[r2].begin();
            if (y > 0) kq += max(y - x, 0);
         }
      }
      printf("%d\n", kq);
      fflush(stdout);
   }
   return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int32_t main()':
regions.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |    int n, r, q; scanf("%d%d%d%d", &n, &r, &q, &a[1]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:42:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |       int x; scanf("%d%d", &x, &a[i]);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:65:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |       int r1, r2; scanf("%d%d", &r1, &r2);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85