oj.uz

Submission #71914

# Submission time Handle Problem Language Result Execution time Memory
71914 2018-08-25T20:48:35 Z Good Min-max tree (BOI18_minmaxtree) C++11
29 / 100
 482 ms 31592 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;

bool vis[Maxn];
bool vis1[Maxn];

int n, q;
int B[Maxn];
int cnt[Maxn];
int lvl[Maxn];
int E[Maxn][2];
int P[Maxn][2];
int mat[Maxn][20];

vector <int> T;
vector <int> S[Maxn];
vector <int> L[Maxn];
vector <int> adj[Maxn];
vector <pair <int, pair <int, pii> > > A[2];

map <int, int> mp;
map <pii, int> mp1;

void dfs (int nd, int p, bool d) {
	mat[nd][0] = p;
	lvl[nd] = lvl[p] + 1;
	
	for (auto i: adj[nd])
		if (i != p) {
			if (d == 1) {	
				cnt[E[i][0]] ++;
				if (E[i][1] != -1 and E[i][0] != -1)
					T.pb (E[i][0]), L[E[i][0]].pb (E[i][1]);	
					
				else if (E[i][0] == -1) {
					vis1[E[i][1]] = 1;
					mp1[{E[i][0], E[i][1]}] = 1;
				}	
			}
					
			dfs (i, nd, d);
		}	
}

void dfs1 (int nd, int p) {
	for (auto i: adj[nd]) {
		if (i != p) {
			if (mp1[{E[i][0], E[i][1]}]) {
				printf ("%d %d %d\n", nd, i, B[E[i][1]]); 
				if (E[i][0] != -1)
					mp1[{E[i][0], E[i][1]}] = 0;
			}	
				
			else 
				printf ("%d %d %d\n", nd, i, B[E[i][0]]);
						
			dfs1 (i, nd);	
		}
	}
}

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);	
}

void solve1 (int ind) {
	int sm = 0;
	for (auto i: L[T[ind]])
		sm += !vis1[i];	
				
	if (sm < cnt[T[ind]]) {
		vis[ind] = 1;
		for (auto i: L[T[ind]])
			if (!vis1[i])
				vis1[i] = 1, mp1[{T[ind], i}] = 1;
		
		for (auto i: L[T[ind]]) {
			while (S[i].size() > 0) {
				int x = S[i].back();
				S[i].ppb();
				if (!vis[x])
					solve1 (x);
			}	
		}		
	}
	
	else
		for (auto i: L[T[ind]])
			if (!vis1[i])
				S[i].pb (ind);			
}

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++) {
		char c;
		int x, y, z;
		
		scanf (" %c%d%d%d", &c, &x, &y, &z);
		mp[z] = 1;
		
		int l = LCA (x, y);
															
		if (c == 'M')
			A[0].pb ({z, {l, {x, y}}});
		else
			A[1].pb ({z, {l, {x, y}}});		
	}
	
	memset (E, -1, sizeof (E));
	
	int c = 1;
	for (auto i: mp)
		B[c] = i.ff, mp[i.ff] = c++;		
	
	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, mp[i.ff], 0);
		solve (i.ss.ss.ss, i.ss.ff, mp[i.ff], 0);	
	}
		
	for (auto i: A[1]) {
		solve (i.ss.ss.ff, i.ss.ff, mp[i.ff], 1);
		solve (i.ss.ss.ss, i.ss.ff, mp[i.ff], 1);
	}
	
	dfs (1, -1, 1);
	T.erase (unique (all (T)), T.end());
	
	for (int i = 0; i < T.size(); i++)
		L[T[i]].erase (unique (all (L[T[i]])), L[T[i]].end());
	
	for (int i = 0; i < T.size(); i++)
		if (!vis[i])
			solve1 (i);
	
	dfs1 (1, -1);		
	return 0;
}

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:215:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++)
                  ~~^~~~~~~~~~
minmaxtree.cpp:218:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++)
                  ~~^~~~~~~~~~
minmaxtree.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
  ~~~~~~^~~~~~~~~~
minmaxtree.cpp:162: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:175:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
minmaxtree.cpp:181:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf (" %c%d%d%d", &c, &x, &y, &z);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11260 KB Output is correct
2 Correct 12 ms 11376 KB Output is correct
3 Correct 13 ms 11376 KB Output is correct
4 Correct 13 ms 11416 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 30248 KB Output is correct
2 Correct 330 ms 30248 KB Output is correct
3 Correct 368 ms 30248 KB Output is correct
4 Correct 482 ms 31592 KB Output is correct
5 Correct 420 ms 31592 KB Output is correct
6 Correct 439 ms 31592 KB Output is correct
7 Correct 380 ms 31592 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 31592 KB Output is correct
2 Correct 212 ms 31592 KB Output is correct
3 Correct 262 ms 31592 KB Output is correct
4 Correct 259 ms 31592 KB Output is correct
5 Correct 244 ms 31592 KB Output is correct
6 Correct 261 ms 31592 KB Output is correct
7 Correct 251 ms 31592 KB Output is correct
8 Incorrect 225 ms 31592 KB Output isn't correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11260 KB Output is correct
2 Correct 12 ms 11376 KB Output is correct
3 Correct 13 ms 11376 KB Output is correct
4 Correct 13 ms 11416 KB Output is correct
5 Correct 416 ms 30248 KB Output is correct
6 Correct 330 ms 30248 KB Output is correct
7 Correct 368 ms 30248 KB Output is correct
8 Correct 482 ms 31592 KB Output is correct
9 Correct 420 ms 31592 KB Output is correct
10 Correct 439 ms 31592 KB Output is correct
11 Correct 380 ms 31592 KB Output is correct
12 Correct 212 ms 31592 KB Output is correct
13 Correct 212 ms 31592 KB Output is correct
14 Correct 262 ms 31592 KB Output is correct
15 Correct 259 ms 31592 KB Output is correct
16 Correct 244 ms 31592 KB Output is correct
17 Correct 261 ms 31592 KB Output is correct
18 Correct 251 ms 31592 KB Output is correct
19 Incorrect 225 ms 31592 KB Output isn't correct