oj.uz

Submission #601221

# Submission time Handle Problem Language Result Execution time Memory
601221 2022-07-21T13:20:46 Z PixelCat Regions (IOI09_regions) C++14
80 / 100
 8000 ms 23756 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;

// 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];

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];
}

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;
}

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);
    while(q--) {
        int r1, r2; cin >> r1 >> r2;
        cout << query_smol(r1, r2) << "\n" << flush;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5600 KB Output is correct
2 Correct 4 ms 5584 KB Output is correct
3 Correct 4 ms 5584 KB Output is correct
4 Correct 5 ms 5584 KB Output is correct
5 Correct 10 ms 5652 KB Output is correct
6 Correct 20 ms 5584 KB Output is correct
7 Correct 41 ms 5584 KB Output is correct
8 Correct 48 ms 5648 KB Output is correct
9 Correct 36 ms 6096 KB Output is correct
10 Correct 61 ms 6012 KB Output is correct
11 Correct 157 ms 6224 KB Output is correct
12 Correct 129 ms 6628 KB Output is correct
13 Correct 200 ms 6352 KB Output is correct
14 Correct 220 ms 6864 KB Output is correct
15 Correct 296 ms 9352 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8077 ms 9552 KB Time limit exceeded
2 Execution timed out 8061 ms 8296 KB Time limit exceeded
3 Execution timed out 8007 ms 11180 KB Time limit exceeded
4 Correct 253 ms 6864 KB Output is correct
5 Correct 318 ms 8504 KB Output is correct
6 Correct 1102 ms 7864 KB Output is correct
7 Correct 1202 ms 8720 KB Output is correct
8 Correct 835 ms 13380 KB Output is correct
9 Correct 1849 ms 13128 KB Output is correct
10 Correct 3848 ms 17816 KB Output is correct
11 Correct 3543 ms 12552 KB Output is correct
12 Correct 3539 ms 14228 KB Output is correct
13 Correct 4303 ms 14488 KB Output is correct
14 Correct 5372 ms 14152 KB Output is correct
15 Correct 6470 ms 18364 KB Output is correct
16 Correct 6098 ms 23756 KB Output is correct
17 Execution timed out 8007 ms 22472 KB Time limit exceeded