Submission #1119521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119521		vjudge1	Min-max tree (BOI18_minmaxtree)	C++17	22 / 100	170 ms	39332 KiB

minmaxtree

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second

using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 2e5 + 5, inf = 1e9;

int n, sz[N], d[N], ind[N], par[N], ct, tp[N], l[N], r[N], node[N];
vector <int> g[N], add[N][2], del[N][2];

void calc(int v, int p = 0) {
	sz[v] = 1;
	par[v] = p;
	for (auto to : g[v]) {
		if (to != p) {
			d[to] = d[v] + 1;
			calc(to, v);
			sz[v] += sz[to];
		}
	}
}
void dfs(int v, int p = 0, int top = 1) {
	ind[v] = ++ct;
	node[ind[v]] = v;
	tp[v] = top;
	int mx = 0, bg = -1;
	for (auto to : g[v]) {
		if (to != p && mx < sz[to]) 
			mx = sz[to], bg = to;
	}
	if (bg != -1)
		dfs(bg, v, top);
	for (auto to : g[v]) {
		if (to != p && to != bg)
			dfs(to, v, to);
	}
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	calc(1);
	dfs(1);
	int q;
	cin >> q;
	while (q--) {
		char c;
		int u, v, z;
		cin >> c >> u >> v >> z;
		
		int mn = inf;
		vector <pii> seg;
		while (tp[u] != tp[v]) {
			if (d[tp[u]] < d[tp[v]]) swap(u, v);
			seg.pb({ind[tp[u]], ind[u]});
			mn = min(mn, seg.back().f);
			u = par[tp[u]];
		}
		if (d[u] > d[v]) swap(u, v);
		seg.pb({ind[u], ind[v]});
		mn = min(mn, seg.back().f);
		
		for (auto [l, r] : seg) {
			if (l == mn)
				++l;
			add[l][(c == 'm')].pb(z);
			del[r + 1][(c == 'm')].pb(z);
		}
	}
	multiset <int> mt[2];
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (auto z : add[i][j])
				mt[j].insert(z);
			for (auto z : del[i][j])
				mt[j].erase(mt[j].find(z));
		}
		r[i] = inf;
		if (sz(mt[0]))
			r[i] = *mt[0].begin();
		if (sz(mt[1]))
			l[i] = *mt[1].rbegin();
	}
	for (int i = 1; i <= n; ++i) {
		if (par[i])
			cout << i << ' ' << par[i] << ' ' << r[ind[i]] << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 22 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42