oj.uz

답안 #281587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
281587 2020-08-23T08:49:59 Z Atalasion Min-max tree (BOI18_minmaxtree) C++14
29 / 100
 378 ms 76912 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){
		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 (st[1][v].size()){
			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]){
			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];
			}
		}
	}
}

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);
	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');
		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 = 0; 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];
		}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++){
		cout << yal[i].F << ' ' << yal[i].S << ' ' << ans[i + 1] << '\n';
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 48888 KB Output is correct
2 Correct 27 ms 48896 KB Output is correct
3 Correct 30 ms 48888 KB Output is correct
4 Correct 27 ms 49024 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 356 ms 74700 KB Output is correct
2 Correct 324 ms 68464 KB Output is correct
3 Correct 326 ms 74988 KB Output is correct
4 Correct 352 ms 76912 KB Output is correct
5 Correct 378 ms 72172 KB Output is correct
6 Correct 320 ms 69116 KB Output is correct
7 Correct 298 ms 68072 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 48888 KB Output is correct
2 Correct 27 ms 48896 KB Output is correct
3 Correct 30 ms 48888 KB Output is correct
4 Correct 27 ms 49024 KB Output is correct
5 Correct 356 ms 74700 KB Output is correct
6 Correct 324 ms 68464 KB Output is correct
7 Correct 326 ms 74988 KB Output is correct
8 Correct 352 ms 76912 KB Output is correct
9 Correct 378 ms 72172 KB Output is correct
10 Correct 320 ms 69116 KB Output is correct
11 Correct 298 ms 68072 KB Output is correct
12 Incorrect 172 ms 63600 KB Output isn't correct
13 Halted 0 ms 0 KB -