제출 #254193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254193		amoo_safar	Min-max tree (BOI18_minmaxtree)	C++14	36 / 100	1093 ms	20892 KiB

minmaxtree

// Null
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const int Inf = 1e9;

int n, k;
int f[N], dep[N];
vector<int> G[N], H[N];

void Prep(int u, int p, int d){
	dep[u] = d;
	f[u] = p;
	for(auto adj : G[u]) if(adj != p) Prep(adj, u, d + 1);
}

int par[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v){
	u = Find(u); v = Find(v);
	if(u == v) return ;
	if(dep[u] < dep[v]) swap(u, v);
	par[u] = v;
}

typedef pair<pair<int, int>, int> T;

vector<T> Q[2];

int L[N], R[N];

int mk[N], match[N];
bool DFS(int u){
	if( (mk[u] == 1) || (u == -1)) return false;
	
	mk[u] = 1;
	
	for(auto adj : H[u]){
		if( (match[adj] == -1) || ( DFS(match[adj]) ) ){
			match[adj] = u;
			return true;
		}
	}
	return false;
}

int Z[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	int u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	Prep(1, 0, 0);
	cin >> k;
	int w;
	char c;
	for(int i = 0; i < k; i++){
		cin >> c >> u >> v >> w;
		Q[(c != 'm')].pb({{u, v}, w});
	}

	iota(par, par + N, 0);
	sort(all(Q[0]), [&](T A, T B){ return A.S > B.S; });
	
	int cnt = 1;
	for(auto X : Q[0]){
		u = X.F.F;
		v = X.F.S;
		w = X.S;
		Z[cnt] = w;
		while(Find(u) != Find(v)){
			if(dep[Find(u)] < dep[Find(v)]) swap(u, v);
			L[Find(u)] = w;
			H[n + cnt].pb(Find(u));
			Unite(Find(u), f[Find(u)]);
		}
		cnt ++;
	}

	fill(R, R + N, Inf);
	iota(par, par + N, 0);
	sort(all(Q[1]), [&](T A, T B){ return A.S < B.S; });
	

	for(auto X : Q[1]){
		u = X.F.F;
		v = X.F.S;
		w = X.S;
		Z[cnt] = w;
		while(Find(u) != Find(v)){
			if(dep[Find(u)] < dep[Find(v)]) swap(u, v);
			R[Find(u)] = w;
			H[n + cnt].pb(Find(u));
			Unite(Find(u), f[Find(u)]);
		}
		cnt ++;
	}
	
	fill(match, match + N, -1);

	for(int i = n + 1; i <= n + k; i++){
		memset(mk, 0, sizeof mk);
		DFS(i);
	}
	//for(int i = 2; i <= n; i++) cerr << match[i] << ' ';
	//cerr << '\n';
	for(int i = 2; i <= n; i++){
		cout << i << ' ' << f[i] << ' ' << (match[i] == -1 ? L[i] : Z[match[i] - n]) << '\n';
	}
	return 0;
}
/*
4
1 2
2 3
3 4
3
M 1 2 1
m 1 4 1
M 2 3 100
*/

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