Submission #1267589

#TimeUsernameProblemLanguageResultExecution timeMemory
1267589AlebnMin-max tree (BOI18_minmaxtree)C++20
0 / 100
202 ms39200 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int,int> #define ff first #define ss second #define all(x) x.begin(),x.end() using namespace std; const int N = 18; struct LCA { int timer; vector<vector<int>> graph, up; vector<int> in, out; LCA(vector<vector<int>>& g):graph(g) { timer = 0; up = vector<vector<int>>(N, vector<int>(g.size())), in = out = vector<int>(g.size()); dfs(0, 0); } void dfs(int i, int p) { in[i] = timer; timer++; up[0][i] = p; for(int j = 1; j < N; j++) up[j][i] = up[j - 1][up[j - 1][i]]; for(auto j : graph[i]) { if(j != p) dfs(j, i); } out[i] = timer; timer++; } bool check(int i, int j) { return in[i] <= in[j] && out[j] <= out[i]; } int lca(int i, int j) { if(check(i, j)) return i; if(check(j, i)) return j; for(int x = N - 1; x >= 0; x--) { if(!check(up[x][i], j)) i = up[x][i]; } return up[0][i]; } }; struct E { int x, y, z; E(int xi, int yi, int zi):x(xi),y(yi),z(zi){} E(){} }; // SUBTASK 2 : ONLY MAXIMUMS signed main() { int n, x, y, k, temp; cin >> n; vector<vector<int>> graph(n); for(int i = 0; i < n - 1; i++) { cin >> x >> y; graph[--x].push_back(--y); graph[y].push_back(x); } cin >> k; char m; LCA lca(graph); vector<int> ks(k); vector<vector<int>> delmi(n), delma(n); vector<set<int>> stmi(n), stma(n); for(int i = 0; i < k; i++) { cin >> m >> x >> y >> ks[i]; if(m == 'M') { delma[lca.lca(--x, --y)].push_back(ks[i]); stma[x].insert(ks[i]); stma[y].insert(ks[i]); } else { delmi[lca.lca(--x, --y)].push_back(ks[i]); stmi[x].insert(ks[i]); stmi[y].insert(ks[i]); } } // dfs dp vector<E> res; res.reserve(n); function<void(int,int)> dfs = [&](int i, int p) { for(auto j : graph[i]) { if(j != p) { dfs(j, i); // push into st[i] if(stma[i].size() < stma[j].size()) swap(stma[i], stma[j]); for(auto x : stma[j]) stma[i].insert(x); if(stmi[i].size() < stmi[j].size()) swap(stmi[i], stmi[j]); for(auto x : stmi[j]) stmi[i].insert(x); } } // apply del[i] for(auto x : delma[i]) stma[i].erase(x); for(auto x : delmi[i]) stmi[i].erase(x); if(i) res.push_back(E(p, i, (stma[i].size() ? *stma[i].begin() : *stmi[i].rbegin()))); }; dfs(0,0); for(auto i : res) cout << i.x + 1 << " " << i.y + 1 << " " << i.z << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...