Submission #1267579

#TimeUsernameProblemLanguageResultExecution timeMemory
1267579AlebnMin-max tree (BOI18_minmaxtree)C++20
0 / 100
209 ms42388 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>> del(n); vector<set<int>> st(n); for(int i = 0; i < k; i++) { cin >> m >> x >> y >> ks[i]; del[lca.lca(--x, --y)].push_back(i); st[x].insert(i); st[y].insert(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(st[i].size() < st[j].size()) swap(st[i], st[j]); for(auto x : st[j]) st[i].insert(x); } } // apply del[i] for(auto x : del[i]) st[i].erase(x); if(i) res.push_back(E(p, i, ks[*st[i].begin()])); }; 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...