제출 #281766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
281766		Atalasion	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	483 ms	85000 KiB

minmaxtree

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 200000 + 10;
const int MOD = 1000000007;
const int LOG = 20;
const int INF = 1000000010;
const int delta = 11353;

int n, m, mn[N], mx[N], par[N][LOG], sz[N], h[N], ans[N], mark[N], W[N], M[N], H[N], PAR[N], PARE[N], M2[N];
vector<pii> G[N], g[N];
vector<int> Tah[2][N], Sar[2][N];
multiset<int> st[2][N];
vector<pii> EE;
map<int, int> mp;
vector<pii> yal;
bool ff = 0;

void DFS(int v = 1, int p = 0){
	par[v][0] = p;
	for (int i = 1; i < LOG; i++) par[v][i] = par[par[v][i - 1]][i - 1];
	for (auto u:G[v]){
		if (u.F == p) continue;
		h[u.F] = h[v] + 1;
		DFS(u.F,v);
	}
}

void dfssz(int v = 1, int p = 0){
	for (auto u:G[v]){
		if(u.F == p) continue;
		dfssz(u.F, v);
		sz[v] += sz[u.F];
	}
}

int LCA(int v, int u){
	if (h[v] < h[u]) swap(v, u);
	int res = h[v] - h[u];
	for (int i = 0; i < LOG; i++) if (res & (1 << i)) v = par[v][i];
	if (v == u) return v;
	for (int i = LOG - 1;  i >= 0; i--){
		if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i];
	}
	return par[v][0];
}

void dfs(int v = 1, int p = 0, int w = 0){
	if (G[v].size() == 1 && v != 1){
		//if(v == 5) cout << Tah[1][v].size() << ' ' << Sar[1][v].size() << '\n';
		for (int j = 0; j < 2; j++){
			for (auto u:Tah[j][v]) st[j][v].insert(u);
			for (auto u:Sar[j][v]) st[j][v].erase(st[j][v].find(u));
		}
		if (st[0][v].size()){
			mx[w] = *st[0][v].begin();
		}
		//if (v == 5) cout << st[1][v].size() << '\n';
		if (st[1][v].size()){
			//cout << w << ' ' << (*st[1][v].rbegin()) << '\n';
			mn[w] = *st[1][v].rbegin();
		}
		return;
	}
	int MX = 0;
	for (auto u:G[v]){
		if(u.F == p) continue;
		dfs(u.F, v, u.S);
		if (sz[MX] < sz[u.F]) MX = u.F;
	}
	for (int j = 0; j < 2; j++){
		st[j][v].swap(st[j][MX]);
		for (auto u:Tah[j][v]) st[j][v].insert(u);
	}
	for (auto u:G[v]){
		if(u.F == p || u.F == MX) continue;
		for (int j = 0; j < 2; j++){
			for (auto x:st[j][u.F]){
				st[j][v].insert(x);
			}
			st[j][u.F].clear();
		}
	}
	for (auto u:Sar[0][v]){
		st[0][v].erase(st[0][v].find(u));
	}
	for (auto u:Sar[1][v]){
		st[1][v].erase(st[1][v].find(u));
	}
	if (st[0][v].size()){
		mx[w] = *st[0][v].begin();
		if (v == 1) assert(0);
	}
	if(st[1][v].size()){
		mn[w] = *st[1][v].rbegin();
		if (v == 1) assert(0);
	}
}

inline int Query(int w){
	return mp[w];
}

void DFS2(int v){
	M[v] = 1;
	mark[v] = 1;
	for (auto u:g[v]){
		if (!M[u.F] && !mark[u.F]){
			DFS2(u.F);
			//cout << "YES " << u.F << ' ' << u.S <<  ' ' << W[u.F] << '\n';
			ans[u.S] = W[u.F];
		}
	}
}

void DFS3(int v){
	M2[v] = 1;
	//cout << v << ' ' << PARE[v] << '\n';
	for(auto u:g[v]){
		if (!M2[u.F]){
			H[u.F] = H[v] + 1;
			PAR[u.F] = v, PARE[u.F] = u.S;
			DFS3(u.F);
		}else if((H[u.F] < H[v]) && ff == 0 && (u.S != PARE[v])){
			//cout << "YES" << endl;
			ff = 1;
			//cout << u.S << '\n';
			ans[u.S] = W[v];
			while (v != u.F){
				mark[v] = 1;
			//	cout << "YES\n";
				ans[PARE[v]] = W[PAR[v]];
				v = PAR[v];
			}
			mark[u.F] = 1;
		}
	}
}

void DFS4(int v){
	M[v] = 1;
	for (auto u:g[v]){
		if (!M[u.F] && !mark[u.F]){
			ans[u.S] = W[u.F];
			DFS4(u.F);
		}
	}
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	sz[0] = -INF;
	fill(mn, mn + N, -INF), fill(mx, mx + N, -INF);
	fill(ans, ans + N, -INF);
	for (int i = 1; i <= n - 1; i++){
		int v, u;
		cin >> v >> u;
		yal.pb({v, u});
		G[v].pb({u, i}), G[u].pb({v, i});
	}
	cin >> m;
	DFS();
	for (int i = 1; i <= m; i++){
		char c;
		int v, u, w;
		cin >> c >> v >> u >> w;
		int lca = LCA(v, u);
		int C = (c == 'm');
	//	cout << C << ' ' << v << ' ' << u << ' ' << lca << '\n';
		Tah[C][v].pb(w), Tah[C][u].pb(w), Sar[C][lca].pb(w), Sar[C][lca].pb(w);
		sz[v]++, sz[u]++, sz[lca]-=2;
		EE.pb({w, i});
		W[i] = w;
		mp[w] = i;
	}
	dfssz();
	dfs();
	//for (int i = 1; i <= n - 1; i++) cout << mn[i] << ' ' << mx[i] << '\n';
	for (int i = 1; i <= n - 1; i++){
		if (mx[i] == -INF || mn[i] == -INF){
			//cout << "YES" << ' ' << mx[i] << ' ' << mn[i] << endl;
			if (mx[i] == -INF && mn[i] != -INF){
				mark[Query(mn[i])] = 1, ans[i] = mn[i];
			//	cout << "YES\n" << Query(mn[i]) << endl;
			}
			if (mx[i] != -INF && mn[i] == -INF){
				mark[Query(mx[i])] = 1, ans[i] = mx[i];
			//	cout << "YES\n" << Query(mx[i]) << '\n';
			}
		}else{
			g[Query(mx[i])].pb({Query(mn[i]), i});
			g[Query(mn[i])].pb({Query(mx[i]), i});
			//cout << Query(mn[i]) << ' ' << Query(mx[i]) << '\n';
		}
	}
	for (int i = 1; i <= m; i++){
		if (mark[i] == 1 && M[i] == 0){
			DFS2(i);
		//	cout << "YES " << i << endl;
		}
	}
	//cout << "YES" << endl;
	for (int i = 1; i <= m; i++){
		if (!M[i] && !M2[i]){
			ff = 0;
		//	cout << "YES2" << endl;
			DFS3(i);
		}
	}
	//cout << "YES" << endl;
	for (int i = 1; i <= m; i++){
		if (mark[i] && !M[i]) DFS4(i);
	}
	for (int i = 0; i < n - 1; i++){
		if (ans[i + 1] == -INF){
			if (mx[i + 1] != -INF) ans[i + 1] = mx[i + 1];
			else if(mn[i + 1] != -INF) ans[i + 1] = mn[i + 1];
			else ans[i + 1] = 0;
		}
		cout << yal[i].F << ' ' << yal[i].S << ' ' << ans[i + 1] << '\n';
	}
	return 0;
}

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