oj.uz

Submission #1119555

# Submission time Handle Problem Language Result Execution time Memory
1119555 2024-11-27T06:39:51 Z vjudge1 Min-max tree (BOI18_minmaxtree) C++17
29 / 100
 202 ms 43212 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);
				}
				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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28496 KB Output is correct
2 Correct 24 ms 28876 KB Output is correct
3 Correct 25 ms 28500 KB Output is correct
4 Correct 23 ms 28500 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 41680 KB Output is correct
2 Correct 202 ms 41136 KB Output is correct
3 Correct 165 ms 43212 KB Output is correct
4 Correct 150 ms 42516 KB Output is correct
5 Correct 163 ms 40968 KB Output is correct
6 Correct 151 ms 41056 KB Output is correct
7 Correct 165 ms 39240 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 38504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28496 KB Output is correct
2 Correct 24 ms 28876 KB Output is correct
3 Correct 25 ms 28500 KB Output is correct
4 Correct 23 ms 28500 KB Output is correct
5 Correct 151 ms 41680 KB Output is correct
6 Correct 202 ms 41136 KB Output is correct
7 Correct 165 ms 43212 KB Output is correct
8 Correct 150 ms 42516 KB Output is correct
9 Correct 163 ms 40968 KB Output is correct
10 Correct 151 ms 41056 KB Output is correct
11 Correct 165 ms 39240 KB Output is correct
12 Incorrect 98 ms 38504 KB Output isn't correct
13 Halted 0 ms 0 KB -