제출 #281766

#제출 시각아이디문제언어결과실행 시간메모리
281766AtalasionMin-max tree (BOI18_minmaxtree)C++14
100 / 100
483 ms85000 KiB
#include <bits/stdc++.h> #define F first #define S second #define pb push_back #define all(x) x.begin(), x.end() #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; const int N = 200000 + 10; const int MOD = 1000000007; const int LOG = 20; const int INF = 1000000010; const int delta = 11353; int n, m, mn[N], mx[N], par[N][LOG], sz[N], h[N], ans[N], mark[N], W[N], M[N], H[N], PAR[N], PARE[N], M2[N]; vector<pii> G[N], g[N]; vector<int> Tah[2][N], Sar[2][N]; multiset<int> st[2][N]; vector<pii> EE; map<int, int> mp; vector<pii> yal; bool ff = 0; void DFS(int v = 1, int p = 0){ par[v][0] = p; for (int i = 1; i < LOG; i++) par[v][i] = par[par[v][i - 1]][i - 1]; for (auto u:G[v]){ if (u.F == p) continue; h[u.F] = h[v] + 1; DFS(u.F,v); } } void dfssz(int v = 1, int p = 0){ for (auto u:G[v]){ if(u.F == p) continue; dfssz(u.F, v); sz[v] += sz[u.F]; } } int LCA(int v, int u){ if (h[v] < h[u]) swap(v, u); int res = h[v] - h[u]; for (int i = 0; i < LOG; i++) if (res & (1 << i)) v = par[v][i]; if (v == u) return v; for (int i = LOG - 1; i >= 0; i--){ if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i]; } return par[v][0]; } void dfs(int v = 1, int p = 0, int w = 0){ if (G[v].size() == 1 && v != 1){ //if(v == 5) cout << Tah[1][v].size() << ' ' << Sar[1][v].size() << '\n'; for (int j = 0; j < 2; j++){ for (auto u:Tah[j][v]) st[j][v].insert(u); for (auto u:Sar[j][v]) st[j][v].erase(st[j][v].find(u)); } if (st[0][v].size()){ mx[w] = *st[0][v].begin(); } //if (v == 5) cout << st[1][v].size() << '\n'; if (st[1][v].size()){ //cout << w << ' ' << (*st[1][v].rbegin()) << '\n'; mn[w] = *st[1][v].rbegin(); } return; } int MX = 0; for (auto u:G[v]){ if(u.F == p) continue; dfs(u.F, v, u.S); if (sz[MX] < sz[u.F]) MX = u.F; } for (int j = 0; j < 2; j++){ st[j][v].swap(st[j][MX]); for (auto u:Tah[j][v]) st[j][v].insert(u); } for (auto u:G[v]){ if(u.F == p || u.F == MX) continue; for (int j = 0; j < 2; j++){ for (auto x:st[j][u.F]){ st[j][v].insert(x); } st[j][u.F].clear(); } } for (auto u:Sar[0][v]){ st[0][v].erase(st[0][v].find(u)); } for (auto u:Sar[1][v]){ st[1][v].erase(st[1][v].find(u)); } if (st[0][v].size()){ mx[w] = *st[0][v].begin(); if (v == 1) assert(0); } if(st[1][v].size()){ mn[w] = *st[1][v].rbegin(); if (v == 1) assert(0); } } inline int Query(int w){ return mp[w]; } void DFS2(int v){ M[v] = 1; mark[v] = 1; for (auto u:g[v]){ if (!M[u.F] && !mark[u.F]){ DFS2(u.F); //cout << "YES " << u.F << ' ' << u.S << ' ' << W[u.F] << '\n'; ans[u.S] = W[u.F]; } } } void DFS3(int v){ M2[v] = 1; //cout << v << ' ' << PARE[v] << '\n'; for(auto u:g[v]){ if (!M2[u.F]){ H[u.F] = H[v] + 1; PAR[u.F] = v, PARE[u.F] = u.S; DFS3(u.F); }else if((H[u.F] < H[v]) && ff == 0 && (u.S != PARE[v])){ //cout << "YES" << endl; ff = 1; //cout << u.S << '\n'; ans[u.S] = W[v]; while (v != u.F){ mark[v] = 1; // cout << "YES\n"; ans[PARE[v]] = W[PAR[v]]; v = PAR[v]; } mark[u.F] = 1; } } } void DFS4(int v){ M[v] = 1; for (auto u:g[v]){ if (!M[u.F] && !mark[u.F]){ ans[u.S] = W[u.F]; DFS4(u.F); } } } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; sz[0] = -INF; fill(mn, mn + N, -INF), fill(mx, mx + N, -INF); fill(ans, ans + N, -INF); for (int i = 1; i <= n - 1; i++){ int v, u; cin >> v >> u; yal.pb({v, u}); G[v].pb({u, i}), G[u].pb({v, i}); } cin >> m; DFS(); for (int i = 1; i <= m; i++){ char c; int v, u, w; cin >> c >> v >> u >> w; int lca = LCA(v, u); int C = (c == 'm'); // cout << C << ' ' << v << ' ' << u << ' ' << lca << '\n'; Tah[C][v].pb(w), Tah[C][u].pb(w), Sar[C][lca].pb(w), Sar[C][lca].pb(w); sz[v]++, sz[u]++, sz[lca]-=2; EE.pb({w, i}); W[i] = w; mp[w] = i; } dfssz(); dfs(); //for (int i = 1; i <= n - 1; i++) cout << mn[i] << ' ' << mx[i] << '\n'; for (int i = 1; i <= n - 1; i++){ if (mx[i] == -INF || mn[i] == -INF){ //cout << "YES" << ' ' << mx[i] << ' ' << mn[i] << endl; if (mx[i] == -INF && mn[i] != -INF){ mark[Query(mn[i])] = 1, ans[i] = mn[i]; // cout << "YES\n" << Query(mn[i]) << endl; } if (mx[i] != -INF && mn[i] == -INF){ mark[Query(mx[i])] = 1, ans[i] = mx[i]; // cout << "YES\n" << Query(mx[i]) << '\n'; } }else{ g[Query(mx[i])].pb({Query(mn[i]), i}); g[Query(mn[i])].pb({Query(mx[i]), i}); //cout << Query(mn[i]) << ' ' << Query(mx[i]) << '\n'; } } for (int i = 1; i <= m; i++){ if (mark[i] == 1 && M[i] == 0){ DFS2(i); // cout << "YES " << i << endl; } } //cout << "YES" << endl; for (int i = 1; i <= m; i++){ if (!M[i] && !M2[i]){ ff = 0; // cout << "YES2" << endl; DFS3(i); } } //cout << "YES" << endl; for (int i = 1; i <= m; i++){ if (mark[i] && !M[i]) DFS4(i); } for (int i = 0; i < n - 1; i++){ if (ans[i + 1] == -INF){ if (mx[i + 1] != -INF) ans[i + 1] = mx[i + 1]; else if(mn[i + 1] != -INF) ans[i + 1] = mn[i + 1]; else ans[i + 1] = 0; } cout << yal[i].F << ' ' << yal[i].S << ' ' << ans[i + 1] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...