oj.uz

Submission #533369

# Submission time Handle Problem Language Result Execution time Memory
533369 2022-03-05T18:18:07 Z guest35178 Regions (IOI09_regions) C++17
100 / 100
 3507 ms 128500 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6856 KB Output is correct
2 Correct 4 ms 6856 KB Output is correct
3 Correct 5 ms 6856 KB Output is correct
4 Correct 8 ms 6984 KB Output is correct
5 Correct 11 ms 6984 KB Output is correct
6 Correct 29 ms 6984 KB Output is correct
7 Correct 31 ms 7016 KB Output is correct
8 Correct 39 ms 6984 KB Output is correct
9 Correct 42 ms 7340 KB Output is correct
10 Correct 71 ms 7496 KB Output is correct
11 Correct 119 ms 7752 KB Output is correct
12 Correct 119 ms 8136 KB Output is correct
13 Correct 158 ms 8264 KB Output is correct
14 Correct 236 ms 8756 KB Output is correct
15 Correct 278 ms 11080 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 11984 KB Output is correct
2 Correct 1778 ms 11712 KB Output is correct
3 Correct 2537 ms 13632 KB Output is correct
4 Correct 296 ms 8648 KB Output is correct
5 Correct 280 ms 10056 KB Output is correct
6 Correct 661 ms 26724 KB Output is correct
7 Correct 1210 ms 30912 KB Output is correct
8 Correct 1325 ms 55380 KB Output is correct
9 Correct 1862 ms 16160 KB Output is correct
10 Correct 3507 ms 128500 KB Output is correct
11 Correct 3234 ms 18500 KB Output is correct
12 Correct 1172 ms 19208 KB Output is correct
13 Correct 1530 ms 19984 KB Output is correct
14 Correct 2153 ms 34300 KB Output is correct
15 Correct 2966 ms 24204 KB Output is correct
16 Correct 2745 ms 29740 KB Output is correct
17 Correct 2530 ms 42612 KB Output is correct