oj.uz

답안 #281593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
281593 2020-08-23T08:53:00 Z Atalasion Min-max tree (BOI18_minmaxtree) C++14
29 / 100
 381 ms 76908 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] && !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);
	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 29 ms 48896 KB Output is correct
2 Correct 31 ms 48888 KB Output is correct
3 Correct 31 ms 48896 KB Output is correct
4 Correct 29 ms 48896 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 366 ms 74700 KB Output is correct
2 Correct 344 ms 68460 KB Output is correct
3 Correct 359 ms 74964 KB Output is correct
4 Correct 381 ms 76908 KB Output is correct
5 Correct 353 ms 72044 KB Output is correct
6 Correct 346 ms 69140 KB Output is correct
7 Correct 322 ms 68200 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 48896 KB Output is correct
2 Correct 31 ms 48888 KB Output is correct
3 Correct 31 ms 48896 KB Output is correct
4 Correct 29 ms 48896 KB Output is correct
5 Correct 366 ms 74700 KB Output is correct
6 Correct 344 ms 68460 KB Output is correct
7 Correct 359 ms 74964 KB Output is correct
8 Correct 381 ms 76908 KB Output is correct
9 Correct 353 ms 72044 KB Output is correct
10 Correct 346 ms 69140 KB Output is correct
11 Correct 322 ms 68200 KB Output is correct
12 Incorrect 191 ms 63724 KB Output isn't correct
13 Halted 0 ms 0 KB -