Submission #1210348

#TimeUsernameProblemLanguageResultExecution timeMemory
1210348NeltBeech Tree (IOI23_beechtree)C++20
9 / 100
2095 ms72308 KiB
#include "beechtree.h" #include <bits/stdc++.h> #define endl "\n" #define ll long long using namespace std; const ll N = 2e5 + 5; vector<ll> g[N]; vector<int> ans; ll c[N], p[N]; ll last[N], ptr[N], sub[N]; vector<pair<ll, ll>> freq[N]; map<ll, ll> col[N]; vector<ll> ord; bool ok; void dfs(ll v) { sub[v] = 1; for (ll to : g[v]) dfs(to), sub[v] += sub[to], col[v][c[to]] = sub[to]; ord.push_back(v); ok &= g[v].size() == col[v].size(); } vector<int> beechtree(int n, int m, vector<int> P, vector<int> C) { for (ll i = 1; i <= n; i++) p[i] = P[i - 1] + 1, c[i] = C[i - 1]; for (ll i = 2; i <= n; i++) g[p[i]].push_back(i); { vector<ll> b; for (ll i = 1; i <= n; i++) b.push_back(c[i]); sort(b.begin(), b.end()); b.resize(unique(b.begin(), b.end()) - b.begin()); for (ll i = 1; i <= n; i++) c[i] = lower_bound(b.begin(), b.end(), c[i]) - b.begin(); m = b.size() - 1; } for (ll i = 1; i <= n; i++) { ok = true; for (ll i = 1; i <= n; i++) col[i].clear(); for (ll j = 1; j <= m; j++) freq[j].clear(); ord.clear(); dfs(i); sort(ord.begin(), ord.end(), [&](ll a, ll b) { return sub[a] >= sub[b]; }); for (ll i = 0; i + 1 < ord.size(); i++) if (sub[ord[i]] == sub[ord[i + 1]]) ok &= col[ord[i]] == col[ord[i + 1]]; else { for (auto [a, b] : col[ord[i]]) ok &= !col[ord[i + 1]].count(a) or col[ord[i + 1]][a] <= b; for (auto [a, b] : col[ord[i + 1]]) ok &= col[ord[i]].count(a) and col[ord[i]][a] >= b; } ans.push_back(ok); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...