Submission #311374

#TimeUsernameProblemLanguageResultExecution timeMemory
311374caoashRegions (IOI09_regions)C++14
55 / 100
7578 ms131072 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; #define pb push_back #define rsz resize #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() using pi = pair<int,int>; #define f first #define s second #define mp make_pair const int MX = 200005; const int MOD = (int) (1e9 + 7); const ll INF = (ll) 1e18; namespace output { void pr(int x) { cout << x; } void pr(long x) { cout << x; } void pr(ll x) { cout << x; } void pr(unsigned x) { cout << x; } void pr(unsigned long x) { cout << x; } void pr(unsigned long long x) { cout << x; } void pr(float x) { cout << x; } void pr(double x) { cout << x; } void pr(long double x) { cout << x; } void pr(char x) { cout << x; } void pr(const char * x) { cout << x; } void pr(const string & x) { cout << x; } void pr(bool x) { pr(x ? "true" : "false"); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x); template < class T > void pr(const T & x); template < class T, class...Ts > void pr(const T & t, const Ts & ...ts) { pr(t); pr(ts...); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x) { pr("{", x.f, ", ", x.s, "}"); } template < class T > void pr(const T & x) { pr("{"); // const iterator needed for vector<bool> bool fst = 1; for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0; pr("}"); } void ps() { pr("\n"); } // print w/ spaces template < class T, class...Ts > void ps(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); } void pc() { cout << "]" << endl; } // debug w/ commas template < class T, class...Ts > void pc(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); } #define dbg(x...) pr("[", #x, "] = ["), pc(x); } #ifdef LOCAL using namespace output; #endif template <class T, int ...Ns> struct BIT { T val = 0; void upd(T v) { val += v; } T query() { return val; } }; template <class T, int N, int... Ns> struct BIT<T, N, Ns...> { BIT<T,Ns...> bit[N+1]; template<typename... Args> void upd(int pos, Args... args) { assert(pos > 0); for (; pos<=N; pos+=pos&-pos) bit[pos].upd(args...); } template<typename... Args> T sum(int r, Args... args) { T res=0; for (;r;r-=r&-r) res += bit[r].query(args...); return res; } template<typename... Args> T query(int l, int r, Args... args) { return sum(r,args...)-sum(l-1,args...); } }; const int B = 500; const int MXR = 25005; vi adj[MX]; int nr[MX], p[MX], good[MXR], st[MX], sz[MX]; int cnt = 0; BIT<int, MX> orz; vi locs[MXR]; map<int, int> vals[MX]; map<pi, int> pre; void dfs_init(int v, int p) { st[v] = cnt++; sz[v] = 1; for (int to : adj[v]) { if (to != p) { dfs_init(to, v); sz[v] += sz[to]; } } } void comb(map<int, int> &a, map<int, int> &b) { if (sz(a) < sz(b)) swap(a, b); for (auto x : b) a.insert(x); b.clear(); } void dfs_merge(int v, int p) { if (good[nr[v]]) vals[v][nr[v]]++; for (int to : adj[v]) { if (to != p) { dfs_merge(to, v); comb(vals[v], vals[to]); } } assert(sz(vals[v]) <= B); if (!good[nr[v]]) { for (auto x : vals[v]) { pre[mp(nr[v], x.f)] += x.s; } } } void dfs_path(int v, int p, map<int, int> &curr) { assert(sz(curr) <= B); for (auto x : curr) { pre[mp(x.f, nr[v])] += x.s; } for (int to : adj[v]) { if (to != p) { if (good[nr[to]]) curr[nr[to]]++; dfs_path(to, v, curr); if (good[nr[to]]) curr[nr[to]]--; } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, r, q; cin >> n >> r >> q; for (int i = 0; i < n; i++) { if (i) { cin >> p[i]; p[i]--; } cin >> nr[i]; nr[i]--; good[nr[i]]++; locs[nr[i]].pb(i); } for (int i = 1; i < n; i++) { adj[p[i]].pb(i); } for (int i = 0; i < r; i++) { if (good[i] > B) good[i] = 1; else good[i] = 0; } dfs_init(0, -1); dfs_merge(0, -1); map<int, int> init; dfs_path(0, -1, init); for (int i = 0; i < q; i++) { int qu, qv; cin >> qu >> qv; qu--, qv--; if (!good[qu] && !good[qv]) { int ret = 0; for (auto p : locs[qv]) { orz.upd(st[p] + 1, 1); // dbg(st[p], 1); } for (auto p : locs[qu]) { ret += orz.query(st[p] + 1, st[p] + sz[p]); // dbg(st[p], st[p] + sz[p] - 1); } for (auto p : locs[qv]) { orz.upd(st[p] + 1, -1); // dbg(st[p], -1); } cout << ret << endl; } else { assert(pre.find(mp(qu, qv)) != pre.end()); cout << pre[mp(qu, qv)] << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...