Submission #299138

#TimeUsernameProblemLanguageResultExecution timeMemory
299138HeheheMin-max tree (BOI18_minmaxtree)C++14
100 / 100
367 ms177860 KiB
#include<bits/stdc++.h> //:3 using namespace std; typedef long long ll; #define all(a) (a).begin(), (a).end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair<int, int> #define sz(x) (int)((x).size()) #define int long long const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; const ll inf = 2e9; const ll mod = 1e9 + 7; const int N = 2e6 + 11; const int X = 1e6; const ll INF64 = 3e18 + 1; const double eps = 1e-14; const double PI = acos(-1); //ifstream in(".in"); //ofstream out(".out"); int depth[N], F[N], l[N], r[N], n, m, k; int E[N*4], lg[N*4], first[N], viz[N], P[N], dp_min[N], dp_max[N]; vector<int> v[N], g[N]; map<int, int> poz; pi rmq[30][N]; struct yes{ int tip, x, y, val; }; yes q[N], w[N]; void dfs(int nod, int p){ E[++k] = nod; first[nod] = k; depth[nod] = depth[p] + 1; F[nod] = P[nod] = p; for(auto it : v[nod]){ if(it == p)continue; dfs(it, nod); E[++k] = nod; } } int get_lca(int x, int y){ int X = first[x], Y = first[y]; if(X > Y)swap(X, Y); int lvl = lg[Y - X + 1]; pi ans = min(rmq[lvl][X], rmq[lvl][Y - (1 << lvl) + 1]); return E[ans.ss]; } int cpl(int nod){ if(viz[nod])return 0; viz[nod] = 1; for(auto it : g[nod]){ if(r[it] == 0 || cpl(r[it])){ l[nod] = it; r[it] = nod; return 1; } } return 0; } void solve(){ cin >> n; for(int i = 1, x, y; i < n; i++){ cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } dfs(1, 0); for(int i = 1; i <= k; i++){ rmq[0][i] = mp(depth[E[i]], i); } for(int i = 1; (1 << i) <= k; i++){ for(int j = 1; j <= k; j++){ rmq[i][j] = rmq[i - 1][j]; if (j + (1 << (i - 1)) <= k && rmq[i - 1][j + (1 << (i - 1))].ff < rmq[i][j].ff) rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))]; } } for(int i = 2; i <= k; i++){ lg[i] = lg[i / 2] + 1; } cin >> m; int el = 0; for(int i = 1, x, y, val; i <= m; i++){ char c; cin >> c >> x >> y >> val; int type = (c == 'M' ? 1 : 0); q[i] = {type, x, y, val}; poz[val] = i; if(type)w[++el] = q[i]; } sort(w + 1, w + el + 1, [](yes L, yes R){ return L.val < R.val; }); for(int i = 1; i <= el; i++){ int x = w[i].x, y = w[i].y, val = w[i].val; int LCA = get_lca(x, y); for(int I : {x, y}){ int nod = I; while (nod && depth[nod] > depth[LCA]){ if(!dp_min[nod])dp_min[nod] = val; int aux = nod; nod = F[nod]; F[aux] = LCA; } } } for(int i = 1; i <= n; i++)F[i] = P[i]; el = 0; for(int i = 1; i <= n; i++){ if(q[i].tip == 0)w[++el] = q[i]; } sort(w + 1, w + el + 1, [](yes L, yes R){ return L.val < R.val; }); for(int i = el; i >= 1; i--){ int x = w[i].x, y = w[i].y, val = w[i].val; int LCA = get_lca(x, y); for(int I : {x, y}){ int nod = I; while (nod && depth[nod] > depth[LCA]){ if(!dp_max[nod])dp_max[nod] = val; int aux = nod; nod = F[nod]; F[aux] = LCA; } } } for(int i = 1; i <= n; i++){ if(dp_max[i]){ int idx = poz[dp_max[i]]; g[i].push_back(n + idx); g[n + idx].push_back (i); } if(dp_min[i]){ int idx = poz[dp_min[i]]; g[i].push_back(n + idx); g[n + idx].push_back(i); } } int ok = 1; while(ok){ memset(viz, 0, sizeof(viz)); ok = 0; for(int i = 1; i <= n; i++){ if(!l[i] && cpl(i))ok = 1; } } for(int i = 2; i <= n; i++){ cout << i << ' ' << P[i] << ' '; int idx = l[i]; cout << (idx ? q[idx - n].val : max(dp_min[i],dp_max[i])) << '\n'; } } int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); //cout << setprecision(6) << fixed; int T = 1; //cin >> T; while(T--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...