oj.uz

Submission #82628

# Submission time Handle Problem Language Result Execution time Memory
82628 2018-11-01T06:08:06 Z Good Min-max tree (BOI18_minmaxtree) C++11
100 / 100
 366 ms 67244 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
#define ff first
#define ss second
#define Maxn 70009
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
#define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> order;

char c[Maxn]; 
bool vis[Maxn];
 
int n, q;
int T[Maxn];
int lvl[Maxn];
int mat[Maxn][20];
int l[Maxn], r[Maxn];
int E[Maxn][2], P[Maxn][2];
int x[Maxn], y[Maxn], z[Maxn];
 
vector <int> M[Maxn];
vector <int> adj[Maxn];
vector <pair <int, pair <int, pii> > > A[2];
 
map <int, int> mp;
 
void dfs (int nd, int p, int d) {
	mat[nd][0] = p;
	lvl[nd] = lvl[p] + 1;
	
	if (d == 1 and nd != 1) {
		if (E[nd][0])
			M[nd].pb (E[nd][0]);
				
		if (E[nd][1])
			M[nd].pb (E[nd][1]);
	}
	
	if (d == 2 and nd != 1) {
		if (!l[nd])
			printf ("%d %d %d\n", p, nd, T[E[nd][1]]);
		else
			printf ("%d %d %d\n", p, nd, T[l[nd]]);	
	}
	
	for (auto i: adj[nd])
		if (i != p)		
			dfs (i, nd, d);
}
 
bool dfs1 (int nd) {
	if (vis[nd])
		return 0;
	
	vis[nd] = 1;	
	for (auto i: M[nd])
		if (!r[i] or dfs1 (r[i])) {
			l[nd] = i;
			r[i] = nd;
			return 1;
		}
	
	return 0;	
} 
 
void build () {
	for (int i = 1; i <= 18; i++)
		for (int j = 1; j <= n; j++)
			if (mat[j][i - 1] != -1)
				mat[j][i] = mat[mat[j][i - 1]][i - 1];	
}
 
int LCA (int a, int b) {
	if (lvl[a] < lvl[b])
		swap (a, b);
		
	for (int i = 18; i >= 0; i--)
		if (lvl[mat[a][i]] >= lvl[b])
			a = mat[a][i];
		
	if (a == b)
		return a;
	
	for (int i = 18; i >= 0; i--)
		if (mat[a][i] != -1 and mat[a][i] != mat[b][i])
			a = mat[a][i], b = mat[b][i];
		
	return mat[a][0];					
}
 
int dsu (int x, bool d) {
	if (P[x][d] == x)
		return x;	
	
	return P[x][d] = dsu (P[x][d], d);	
}
 
void solve (int x, int y, int z, bool d) {
	x = dsu (P[x][d], d);
			
	if (lvl[x] <= lvl[y])
		return;		
	
	E[x][d] = z;
	
	if (mat[x][0] != -1)
		P[x][d] = dsu (mat[x][0], d);
	
	x = P[x][d];
	
	solve (x, y, z, d);	
}
 
int main () {
	//freopen ("file.in", "r", stdin);
	//freopen ("file.out", "w", stdout);
	
 	//srand ((unsigned) time ( NULL ));
	//int randomNumber = rand() % 10 + 1;
 
	scanf ("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf ("%d%d", &u, &v);
		
		adj[u].pb (v);
		adj[v].pb (u);
		P[i][0] = P[i][1] = i;
	}
	
	P[n][0] = P[n][1] = n;
	
	memset (mat, -1, sizeof (mat));
	dfs (1, -1, 0);
	build ();
	
	scanf ("%d", &q);
	
	for (int i = 1; i <= q; i++) {		
		scanf (" %c%d%d%d", &c[i], &x[i], &y[i], &z[i]);
		mp[z[i]] = 1;	
	}
	
	int cnt = 0;
	for (auto i: mp)
		mp[i.ff] = ++cnt;
	
	for (int i = 1; i <= q; i++) {
		int l = LCA (x[i], y[i]);
		
		if (c[i] == 'M')
			A[0].pb ({mp[z[i]], {l, {x[i], y[i]}}});
		else
			A[1].pb ({mp[z[i]], {l, {x[i], y[i]}}});		
		
		T[mp[z[i]]] = z[i];
	}
	
	sort (all (A[0]));
	sort (all (A[1]));
	reverse (all (A[1]));
	
	for (auto i: A[0]) {
		solve (i.ss.ss.ff, i.ss.ff, i.ff, 0);
		solve (i.ss.ss.ss, i.ss.ff, i.ff, 0);	
	}
		
	for (auto i: A[1]) {
		solve (i.ss.ss.ff, i.ss.ff, i.ff, 1);
		solve (i.ss.ss.ss, i.ss.ff, i.ff, 1);
	}
	
	dfs (1, -1, 1);
	
	bool ok = 1;
	while (ok) {
		ok = 0;
		memset (vis, 0, sizeof (vis));
		
		for (int i = 2; i <= n; i++)
			if (!l[i] and dfs1 (i))
				ok = 1;
	}

	dfs (1, -1, 2);	
	return 0;
}

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
  ~~~~~~^~~~~~~~~~
minmaxtree.cpp:134:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &u, &v);
   ~~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
minmaxtree.cpp:150:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf (" %c%d%d%d", &c[i], &x[i], &y[i], &z[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9212 KB Output is correct
2 Correct 10 ms 9248 KB Output is correct
3 Correct 9 ms 9452 KB Output is correct
4 Correct 9 ms 9452 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 24556 KB Output is correct
2 Correct 255 ms 24556 KB Output is correct
3 Correct 286 ms 24556 KB Output is correct
4 Correct 300 ms 25112 KB Output is correct
5 Correct 278 ms 25112 KB Output is correct
6 Correct 268 ms 25112 KB Output is correct
7 Correct 240 ms 25112 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 25112 KB Output is correct
2 Correct 168 ms 25112 KB Output is correct
3 Correct 148 ms 25112 KB Output is correct
4 Correct 177 ms 25112 KB Output is correct
5 Correct 202 ms 25112 KB Output is correct
6 Correct 223 ms 25964 KB Output is correct
7 Correct 194 ms 26804 KB Output is correct
8 Correct 173 ms 28084 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9212 KB Output is correct
2 Correct 10 ms 9248 KB Output is correct
3 Correct 9 ms 9452 KB Output is correct
4 Correct 9 ms 9452 KB Output is correct
5 Correct 281 ms 24556 KB Output is correct
6 Correct 255 ms 24556 KB Output is correct
7 Correct 286 ms 24556 KB Output is correct
8 Correct 300 ms 25112 KB Output is correct
9 Correct 278 ms 25112 KB Output is correct
10 Correct 268 ms 25112 KB Output is correct
11 Correct 240 ms 25112 KB Output is correct
12 Correct 154 ms 25112 KB Output is correct
13 Correct 168 ms 25112 KB Output is correct
14 Correct 148 ms 25112 KB Output is correct
15 Correct 177 ms 25112 KB Output is correct
16 Correct 202 ms 25112 KB Output is correct
17 Correct 223 ms 25964 KB Output is correct
18 Correct 194 ms 26804 KB Output is correct
19 Correct 173 ms 28084 KB Output is correct
20 Correct 319 ms 34624 KB Output is correct
21 Correct 262 ms 35224 KB Output is correct
22 Correct 247 ms 37400 KB Output is correct
23 Correct 241 ms 39572 KB Output is correct
24 Correct 338 ms 45120 KB Output is correct
25 Correct 330 ms 48648 KB Output is correct
26 Correct 281 ms 50188 KB Output is correct
27 Correct 366 ms 52024 KB Output is correct
28 Correct 331 ms 52912 KB Output is correct
29 Correct 314 ms 55516 KB Output is correct
30 Correct 259 ms 56136 KB Output is correct
31 Correct 278 ms 58492 KB Output is correct
32 Correct 273 ms 61792 KB Output is correct
33 Correct 267 ms 63456 KB Output is correct
34 Correct 290 ms 65692 KB Output is correct
35 Correct 277 ms 67244 KB Output is correct