oj.uz

Submission #601233

# Submission time Handle Problem Language Result Execution time Memory
601233 2022-07-21T13:30:47 Z PixelCat Regions (IOI09_regions) C++14
50 / 100
 2735 ms 131072 KB 
/*       code by the cute PixelCat owo       */
/*   as cute as nacho neko (aka. my wife)!   */

// #pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
using uLL = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

// #define MOD (int)(998244353)
#define MOD (int)(1e9 + 7)
// #define INF (int)(9000000000000000000ll)  // 9e18
#define INF (int)(1000000000000000000ll)  // 1e18
#define EPS (1e-6)

#ifdef NYAOWO
#include "../library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod = MOD) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * b % mod;
        p /= 2;
        b = b * b % mod;
    }
    return ans;
}
int fpow(int b, int p) {
    return fpow(b, p, MOD);
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
// static mt19937_64 rng(
//     chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 200020;
const int MAXR = 25020;
const int K = 38;

#define IS_BIG(R) (sz(pos[R]) >= K)

// tree
vector<int32_t> adj[MAXN];
int16_t t_col[MAXN];

// euler tour
int32_t size[MAXN];
int16_t color[MAXN];
vector<int32_t> pos[MAXR];

int32_t buf[MAXN];
map<int, map<int, int>> ans_big; // {r1 -> {r2 -> ans}}

int buildEulerTour(int cur) {
    static int now_id = 1;
    int id = now_id; now_id++;
    size[id] = 1;
    color[id] = t_col[cur];
    pos[color[id]].eb(id);
    for(auto &i:adj[cur]) {
        size[id] += buildEulerTour(i);
    }
    return size[id];
}

void precal_big(int r, int n) {
    memset(buf, 0, sizeof(buf));
    for(auto &i:pos[r]) {
        buf[i + 1]++;
        buf[i + size[i]]--;
    }
    For(i, 1, n) {
        buf[i] += buf[i - 1];
        ans_big[r][color[i]] += buf[i];
    }
}

inline int count(int col, int l, int r) {
    return upper_bound(all(pos[col]), r) - lower_bound(all(pos[col]), l);
}

int query_smol(int r1, int r2) {
    int ans = 0;
    for(auto &i:pos[r1]) {
        ans += count(r2, i + 1, i + size[i] - 1);
    }
    return ans;
}

int query_big(int r1, int r2) {
    return ans_big[r1][r2];
}

int32_t main() {
    NYA();
    // QAQ
    int n, r, q;
    cin >> n >> r >> q;
    cin >> t_col[1];
    For(i, 2, n) {
        int p; cin >> p;
        adj[p].eb(i);
        cin >> t_col[i];
    }
    buildEulerTour(1);
    For(i, 1, r) if(IS_BIG(i)) {
        precal_big(i, n);
    }
    while(q--) {
        int r1, r2; cin >> r1 >> r2;
        if(IS_BIG(r1)) {
            cout << query_big(r1, r2) << "\n" << flush;
        } else {
            cout << query_smol(r1, r2) << "\n" << flush;
        }
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 4 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 10 ms 5584 KB Output is correct
6 Correct 16 ms 5584 KB Output is correct
7 Correct 31 ms 5584 KB Output is correct
8 Correct 30 ms 5712 KB Output is correct
9 Correct 23 ms 6096 KB Output is correct
10 Correct 75 ms 6736 KB Output is correct
11 Correct 367 ms 11568 KB Output is correct
12 Correct 656 ms 18268 KB Output is correct
13 Correct 669 ms 14312 KB Output is correct
14 Correct 468 ms 10144 KB Output is correct
15 Correct 727 ms 13636 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1316 ms 12780 KB Output is correct
2 Correct 1563 ms 11992 KB Output is correct
3 Correct 2409 ms 16448 KB Output is correct
4 Correct 499 ms 30196 KB Output is correct
5 Correct 1710 ms 82084 KB Output is correct
6 Correct 673 ms 31696 KB Output is correct
7 Correct 1986 ms 88348 KB Output is correct
8 Runtime error 1862 ms 131072 KB Execution killed with signal 9
9 Runtime error 2523 ms 131072 KB Execution killed with signal 9
10 Runtime error 1552 ms 131072 KB Execution killed with signal 9
11 Runtime error 2288 ms 131072 KB Execution killed with signal 9
12 Runtime error 2735 ms 131072 KB Execution killed with signal 9
13 Runtime error 2710 ms 131072 KB Execution killed with signal 9
14 Runtime error 2351 ms 131072 KB Execution killed with signal 9
15 Runtime error 1784 ms 131072 KB Execution killed with signal 9
16 Runtime error 1653 ms 131072 KB Execution killed with signal 9
17 Runtime error 2175 ms 131072 KB Execution killed with signal 9