Submission #1097303

#TimeUsernameProblemLanguageResultExecution timeMemory
1097303DaciejMaciejRegions (IOI09_regions)C++17
100 / 100
3018 ms34688 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef long double ld; template <class T> using VV = vector<vector<T>>; using VI = vector<int>; using VVI = vector<vector<int>>; using VL = vector<long long>; using VVL = vector<vector<long long>>; using VC = vector<char>; using VVC = vector<vector<char>>; using VB = vector<bool>; using VVB = vector<vector<bool>>; using VD = vector<double>; using VVD = vector<vector<double>>; using PII = pair<int, int>; using PLL = pair<long long, long long>; using PIL = pair<int, long long>; using PLI = pair<long long, int>; using VPII = vector<pair<int, int>>; using VPLL = vector<pair<long long, long long>>; #define LINE '\n' #define SPACE ' ' #define PB push_back #define FOR(i, a, b) for (int i = (a); i < (int(b)); i++) #define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++) #define ALL(x) x.begin(), x.end() #define RALL(x) x.rbegin(), x.rend() #define sq(a) ((a) * (a)) #define sz(x) ((int)x.size()) #define fastio() \ ios_base::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr) #define debug(x) cerr << #x << " = " << x << endl; // zero indexed template <class T> struct SegTree { const T def = 0; int n; vector<T> seg; SegTree(int _size) : n(_size), seg(2 * _size, def) {} inline T merge(T a, T b) { return max(a, b); } void update(int pos, T val) { for (seg[pos += n] = val; pos /= 2;) { seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]); } } T query(int l, int r) // get [l, r] { T a = def, b = def; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l % 2) a = merge(a, seg[l++]); if (r % 2) b = merge(b, seg[--r]); } return merge(a, b); } }; template <class T> struct BIT { int size; vector<T> bit; vector<T> arr; BIT(int _size) : size(_size), bit(_size + 1), arr(_size) {} void set(int pos, T val) { add(pos, val - arr[pos]); } void add(int pos, T val) { arr[pos] += val; for (pos++; pos <= size; pos += pos & -pos) { bit[pos] += val; } } T query(int pos) { T res = 0; for (pos++; pos > 0; pos -= pos & -pos) { res += bit[pos]; } return res; } }; const ll MOD = 1e9 + 7; template <class T> inline void maxi(T &a, T b) { a = max(a, b); } template <class T> inline void mini(T &a, T b) { a = min(a, b); } template <class T> inline void addi(T &a, T b) { a = (a + b) % MOD; } template <class T> inline void subi(T &a, T b) { a = (a - b + MOD) % MOD; } template <class T> inline T add(T a, T b) { return (a + b) % MOD; } template <class T> inline T sub(T a, T b) { return (a - b + MOD) % MOD; } template <class T> inline T mul(T a, T b) { return ((a % MOD) * (b % MOD)) % MOD; } constexpr ll binpow(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1) { res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } const int INF = 1e9; const int MAX_N = 1e5 + 3; void solve() { int n, r, q; cin >> n >> r >> q; VI region(n); VV<int> g(n); cin >> region[0]; region[0]--; FOR(i, 1, n) { int p, h; cin >> p >> h; p--, h--; g[p].PB(i); region[i] = h; } /* tin - in time tout - out time rtin - rtin[tin[u]] = u rg - for each region list of tin vecs */ VI tin(n), tout(n), rtin(n); VV<int> rg(r); int t = 0; function<void(int)> dfs = [&](int c) -> void { tin[c] = t++; rtin[tin[c]] = c; rg[region[c]].PB(tin[c]); for (auto v : g[c]) { dfs(v); } tout[c] = t; }; dfs(0); const int BS = sqrt(n); VV<int> pre; // pre[id][reg] = ans for query a, b VI rid(r, -1); // compress regions ids int id = 0; function<void(int, int, int)> dfs2 = [&](int c, int pr, int p_size) -> void { if (region[c] == pr) { p_size++; } pre[rid[pr]][region[c]] += p_size; for (auto v : g[c]) dfs2(v, pr, p_size); }; FOR(i, 0, r) { if (sz(rg[i]) < BS) continue; rid[i] = id++; pre.PB(VI(r, 0)); dfs2(0, i, 0); } FOR(i, 0, q) { int a, b; cin >> a >> b; a--, b--; if (rid[a] != -1) { cout << pre[rid[a]][b] << LINE; } else { int rs = 0; for (auto v : rg[a]) { // v is the in time for region a rs += lower_bound(ALL(rg[b]), tout[rtin[v]]) - lower_bound(ALL(rg[b]), tin[rtin[v]]); } cout << rs << LINE; } } } int main() { // fastio(); int t = 1; // cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...