Submission #601233

#	Time	Username	Problem	Language	Result	Execution time	Memory
601233		PixelCat	Regions (IOI09_regions)	C++14	50 / 100	2735 ms	131072 KiB

regions

/*       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 / 15
• Subtask 2: 35 / 85