oj.uz

답안 #1119537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1119537 2024-11-27T06:25:41 Z vjudge1 Min-max tree (BOI18_minmaxtree) C++17
22 / 100
 177 ms 45128 KB 
#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);
					cout << i << ' ' << j + q << '\n';
				}
				if (c == 'M' && r[j] == z) {
					cout << i << ' ' << j + q << '\n';
					gg[i].pb(j + q);
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i)
		Mt[i] = -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
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 28496 KB Integer 0 violates the range [1, 20]
2 Halted 0 ms 0 KB -

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 43984 KB Output is correct
2 Correct 177 ms 43444 KB Output is correct
3 Correct 147 ms 44612 KB Output is correct
4 Correct 120 ms 45128 KB Output is correct
5 Correct 126 ms 42992 KB Output is correct
6 Correct 126 ms 41968 KB Output is correct
7 Correct 143 ms 41796 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 39492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 28496 KB Integer 0 violates the range [1, 20]
2 Halted 0 ms 0 KB -