oj.uz

Submission #254193

# Submission time Handle Problem Language Result Execution time Memory
254193 2020-07-29T13:45:06 Z amoo_safar Min-max tree (BOI18_minmaxtree) C++14
36 / 100
 1000 ms 20892 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], match[N];
bool DFS(int u){
	if( (mk[u] == 1) || (u == -1)) return false;
	
	mk[u] = 1;
	
	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);
		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 1
M 2 3 100
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Correct 9 ms 13056 KB Output is correct
4 Correct 8 ms 12928 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 20696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 18384 KB Output is correct
2 Correct 613 ms 18448 KB Output is correct
3 Correct 509 ms 19928 KB Output is correct
4 Correct 476 ms 20892 KB Output is correct
5 Correct 874 ms 18864 KB Output is correct
6 Correct 759 ms 19180 KB Output is correct
7 Correct 704 ms 18552 KB Output is correct
8 Correct 697 ms 18580 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Correct 9 ms 13056 KB Output is correct
4 Correct 8 ms 12928 KB Output is correct
5 Execution timed out 1093 ms 20696 KB Time limit exceeded
6 Halted 0 ms 0 KB -