Submission #918884

#TimeUsernameProblemLanguageResultExecution timeMemory
918884ShaShiRegions (IOI09_regions)C++17
100 / 100
3633 ms105148 KiB
#include <bits/stdc++.h> // #define int long long #define F first #define S second #define pii pair<int, int> #define all(x) x.begin(), x.end() #define kill(x) cout << x << endl, exit(0); #define mp make_pair #define pb push_back // #define endl "\n" using namespace std; typedef long long ll; const int MAXN = (int)2e5 + 7; const int MOD = 999999893; const int INF = (int)1e9 + 7; const int SQ = 450; int n, m, t, flag, u, v, w, k, tmp, tmp2, tmp3, tmp4, tmp5, tmp6, ans, q, ans2; int arr[MAXN], num[MAXN], id[MAXN], st[MAXN], ft[MAXN]; int res[SQ][MAXN]; vector<int> adj[MAXN], col[MAXN], vec[MAXN]; void DFSsz(int v) { st[v] = flag; vec[arr[v]].pb(flag++); for (int u:adj[v]) DFSsz(u); ft[v] = flag; } void DFS(int v, int x, int id, int bala) { res[id][arr[v]] += bala; bala += (arr[v] == x); for (int u:adj[v]) DFS(u, x, id, bala); } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> q; cin >> arr[1]; col[arr[1]].pb(1); num[arr[1]]++; for (int i=2; i<=n; i++) { cin >> u >> arr[i]; adj[u].pb(i); col[arr[i]].pb(i); num[arr[i]]++; } DFSsz(1); flag = 0; for (int i=1; i<=m; i++) { if (num[i] >= SQ) { id[i] = flag; DFS(1, i, flag, 0); flag++; } } for (int i=1; i<=m; i++) vec[i].pb(INF); while (q--) { cin >> u >> v; // cout << "!"; if (num[u] < SQ) { ans = 0; for (int w:col[u]) ans += lower_bound(all(vec[v]), ft[w])-lower_bound(all(vec[v]), st[w]); cout << ans << endl; } else { cout << res[id[u]][v] << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...