제출 #1119555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119555		vjudge1	Min-max tree (BOI18_minmaxtree)	C++17	29 / 100	202 ms	43212 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], gg[N], add[N][2], del[N][2];
char C[N];
int U[N], V[N], Z[N], used[N], timer, Mt[N];

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);
	}
}

bool kuhn(int v) {
	if (used[v] == timer)
		return 0;
	used[v] = timer;
	for (auto to : gg[v]) {
		if (Mt[to] == -1) {
			Mt[to] = v;
			return 1;
		}
	}
	for (auto to : gg[v]) {
		if (kuhn(Mt[to])) {
			Mt[to] = v;
			return 1;
		}
	}
	return 0;
}

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;
	for (int i = 0; i < q; ++i) {
		char c;
		int u, v, z;
		cin >> c >> u >> v >> z;
		C[i] = c;
		U[i] = u;
		V[i] = v;
		Z[i] = 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();
	}
	if (n > 1000) {
		for (int i = 1; i <= n; ++i) {
			if (par[i])
				cout << i << ' ' << par[i] << ' ' << r[ind[i]] << '\n';
		}
		return 0;
	}
	for (int i = 0; i < q; ++i) {
		char c;
		int u, v, z;
		c = C[i];
		u = U[i];
		v = V[i];
		z = Z[i];
		
		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 [x, y] : seg) {
			if (x == mn)
				++x;
			
			for (int j = x; j <= y; ++j) {
				if (c == 'm' && l[j] == z) {
					gg[i].pb(j + q);
				}
				if (c == 'M' && r[j] == z) {
					gg[i].pb(j + q);
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i)
		Mt[i + q] = -1;
	for (int i = 0; i < q; ++i) {
		++timer;
		kuhn(i);
	}
	for (int i = 1; i <= n; ++i) {
		if (!par[i])
			continue;
		if (Mt[ind[i] + q] == -1)
			cout << i << ' ' << par[i] << ' ' << l[ind[i]] << '\n';
		else
			cout << i << ' ' << par[i] << ' ' << Z[Mt[ind[i] + q]] << '\n';
	}
	return 0;
}

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