oj.uz

Submission #814371

# Submission time Handle Problem Language Result Execution time Memory
814371 2023-08-08T07:06:52 Z qthang2k11 Regions (IOI09_regions) C++17
100 / 100
 3338 ms 128508 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6864 KB Output is correct
2 Correct 3 ms 6864 KB Output is correct
3 Correct 5 ms 6940 KB Output is correct
4 Correct 8 ms 6992 KB Output is correct
5 Correct 11 ms 6996 KB Output is correct
6 Correct 21 ms 6992 KB Output is correct
7 Correct 17 ms 7012 KB Output is correct
8 Correct 34 ms 6992 KB Output is correct
9 Correct 34 ms 7376 KB Output is correct
10 Correct 84 ms 7456 KB Output is correct
11 Correct 100 ms 7760 KB Output is correct
12 Correct 132 ms 8264 KB Output is correct
13 Correct 126 ms 8272 KB Output is correct
14 Correct 235 ms 8776 KB Output is correct
15 Correct 222 ms 11088 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1596 ms 11956 KB Output is correct
2 Correct 1901 ms 11720 KB Output is correct
3 Correct 2180 ms 13688 KB Output is correct
4 Correct 244 ms 8632 KB Output is correct
5 Correct 333 ms 10092 KB Output is correct
6 Correct 505 ms 26560 KB Output is correct
7 Correct 1086 ms 30872 KB Output is correct
8 Correct 1278 ms 55252 KB Output is correct
9 Correct 1924 ms 16068 KB Output is correct
10 Correct 3271 ms 128508 KB Output is correct
11 Correct 3338 ms 18324 KB Output is correct
12 Correct 1043 ms 19212 KB Output is correct
13 Correct 1629 ms 19984 KB Output is correct
14 Correct 1934 ms 34308 KB Output is correct
15 Correct 2290 ms 24264 KB Output is correct
16 Correct 2651 ms 29756 KB Output is correct
17 Correct 2539 ms 42584 KB Output is correct