oj.uz

Submission #254195

# Submission time Handle Problem Language Result Execution time Memory
254195 2020-07-29T13:48:23 Z amoo_safar Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 119 ms 23212 KB 
// 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], Tm = 1, match[N];
bool DFS(int u){
	if( (mk[u] == Tm) ) return false;
	mk[u] = Tm;

	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);
		Tm ++;
		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 0
M 2 3 100
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 9 ms 12032 KB Output is correct
3 Correct 7 ms 12032 KB Output is correct
4 Correct 8 ms 12032 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 21736 KB Output is correct
2 Correct 100 ms 19944 KB Output is correct
3 Correct 112 ms 20456 KB Output is correct
4 Correct 110 ms 22248 KB Output is correct
5 Correct 93 ms 20336 KB Output is correct
6 Correct 106 ms 20308 KB Output is correct
7 Correct 96 ms 19816 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 17876 KB Output is correct
2 Correct 69 ms 17784 KB Output is correct
3 Correct 71 ms 19288 KB Output is correct
4 Correct 72 ms 20192 KB Output is correct
5 Correct 74 ms 18092 KB Output is correct
6 Correct 76 ms 18544 KB Output is correct
7 Correct 75 ms 17912 KB Output is correct
8 Correct 74 ms 17812 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 9 ms 12032 KB Output is correct
3 Correct 7 ms 12032 KB Output is correct
4 Correct 8 ms 12032 KB Output is correct
5 Correct 104 ms 21736 KB Output is correct
6 Correct 100 ms 19944 KB Output is correct
7 Correct 112 ms 20456 KB Output is correct
8 Correct 110 ms 22248 KB Output is correct
9 Correct 93 ms 20336 KB Output is correct
10 Correct 106 ms 20308 KB Output is correct
11 Correct 96 ms 19816 KB Output is correct
12 Correct 66 ms 17876 KB Output is correct
13 Correct 69 ms 17784 KB Output is correct
14 Correct 71 ms 19288 KB Output is correct
15 Correct 72 ms 20192 KB Output is correct
16 Correct 74 ms 18092 KB Output is correct
17 Correct 76 ms 18544 KB Output is correct
18 Correct 75 ms 17912 KB Output is correct
19 Correct 74 ms 17812 KB Output is correct
20 Correct 102 ms 20280 KB Output is correct
21 Correct 86 ms 19508 KB Output is correct
22 Correct 87 ms 19504 KB Output is correct
23 Correct 90 ms 19560 KB Output is correct
24 Correct 114 ms 22244 KB Output is correct
25 Correct 119 ms 23212 KB Output is correct
26 Correct 104 ms 22832 KB Output is correct
27 Correct 109 ms 21928 KB Output is correct
28 Correct 119 ms 20452 KB Output is correct
29 Correct 111 ms 20668 KB Output is correct
30 Correct 101 ms 19892 KB Output is correct
31 Correct 110 ms 19828 KB Output is correct
32 Correct 109 ms 20300 KB Output is correct
33 Correct 100 ms 19884 KB Output is correct
34 Correct 100 ms 19824 KB Output is correct
35 Correct 97 ms 19636 KB Output is correct