oj.uz

답안 #281766

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
281766 2020-08-23T12:48:53 Z Atalasion Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 483 ms 85000 KB 
#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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 49656 KB Output is correct
2 Correct 30 ms 49656 KB Output is correct
3 Correct 31 ms 49656 KB Output is correct
4 Correct 30 ms 49664 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 383 ms 77548 KB Output is correct
2 Correct 383 ms 71412 KB Output is correct
3 Correct 363 ms 77548 KB Output is correct
4 Correct 387 ms 79720 KB Output is correct
5 Correct 352 ms 74728 KB Output is correct
6 Correct 343 ms 72084 KB Output is correct
7 Correct 308 ms 71144 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 65388 KB Output is correct
2 Correct 186 ms 65692 KB Output is correct
3 Correct 188 ms 70636 KB Output is correct
4 Correct 202 ms 73572 KB Output is correct
5 Correct 206 ms 67308 KB Output is correct
6 Correct 219 ms 68456 KB Output is correct
7 Correct 206 ms 66284 KB Output is correct
8 Correct 216 ms 66028 KB Output is correct

Subtask #4
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 49656 KB Output is correct
2 Correct 30 ms 49656 KB Output is correct
3 Correct 31 ms 49656 KB Output is correct
4 Correct 30 ms 49664 KB Output is correct
5 Correct 383 ms 77548 KB Output is correct
6 Correct 383 ms 71412 KB Output is correct
7 Correct 363 ms 77548 KB Output is correct
8 Correct 387 ms 79720 KB Output is correct
9 Correct 352 ms 74728 KB Output is correct
10 Correct 343 ms 72084 KB Output is correct
11 Correct 308 ms 71144 KB Output is correct
12 Correct 179 ms 65388 KB Output is correct
13 Correct 186 ms 65692 KB Output is correct
14 Correct 188 ms 70636 KB Output is correct
15 Correct 202 ms 73572 KB Output is correct
16 Correct 206 ms 67308 KB Output is correct
17 Correct 219 ms 68456 KB Output is correct
18 Correct 206 ms 66284 KB Output is correct
19 Correct 216 ms 66028 KB Output is correct
20 Correct 389 ms 73732 KB Output is correct
21 Correct 315 ms 73196 KB Output is correct
22 Correct 352 ms 74992 KB Output is correct
23 Correct 321 ms 72940 KB Output is correct
24 Correct 483 ms 82192 KB Output is correct
25 Correct 480 ms 85000 KB Output is correct
26 Correct 409 ms 83180 KB Output is correct
27 Correct 453 ms 80620 KB Output is correct
28 Correct 430 ms 75480 KB Output is correct
29 Correct 428 ms 75572 KB Output is correct
30 Correct 368 ms 72812 KB Output is correct
31 Correct 391 ms 72808 KB Output is correct
32 Correct 446 ms 74604 KB Output is correct
33 Correct 398 ms 75500 KB Output is correct
34 Correct 434 ms 75548 KB Output is correct
35 Correct 362 ms 73320 KB Output is correct