Submission #533369

#	Time	Username	Problem	Language	Result	Execution time	Memory
533369		guest35178	Regions (IOI09_regions)	C++17	100 / 100	3507 ms	128500 KiB

regions

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

const int mod = 1e9+7;
const int N = 2e5+16;
const int R = 2.5e4+16;
const int inf = 1e9+16;

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);
    }
};
#define pb push_back
// bien
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;
}

void solve() {
   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].pb(i);
      adj[i].pb(x);
   }
   dfs(1, 1);
   for (int i = 1; i <= n; i++)
      re[a[node[i]]].pb(i);
   int sq = sqrt(n);
   for (int i = 1; i <= n; i++) {
      int x = node[i], r = a[x];
      if (vs[r] || 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 (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);
   }
}

int32_t main() {
   #ifdef _LOCAL_
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
   #endif

   int nTest = 1;
   // cin >> nTest;
   while (nTest--) {
      solve();
   }

   return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void solve()':
regions.cpp:57:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |       if (vs[r] || re[r].size() <= sq) continue;
      |                    ~~~~~~~~~~~~~^~~~~
regions.cpp:72:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |       if (re[r1].size() > sq) kq = ans[r1][r2];
      |           ~~~~~~~~~~~~~~^~~~
regions.cpp:45:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |    int n, r, q; scanf("%d%d%d%d", &n, &r, &q, &a[1]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:47:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |       int x; scanf("%d%d", &x, &a[i]);
      |              ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:70:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |       int r1, r2; scanf("%d%d", &r1, &r2);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~

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