oj.uz

Submission #72620

# Submission time Handle Problem Language Result Execution time Memory
72620 2018-08-26T12:00:57 Z Good Min-max tree (BOI18_minmaxtree) C++11
29 / 100
 533 ms 31564 KB 
#include <bits/stdc++.h>

#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
using namespace std;

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]}]) {
				if (E[i][1] == -1 and E[i][0] != -1)
					assert (0);
				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 {
				if (E[i][0] == -1 and E[i][1] != -1)
					assert (0);
					
				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:216:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++)
                  ~~^~~~~~~~~~
minmaxtree.cpp:219:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++)
                  ~~^~~~~~~~~~
minmaxtree.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
  ~~~~~~^~~~~~~~~~
minmaxtree.cpp:163: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:176:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
minmaxtree.cpp:182: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 11 ms 11260 KB Output is correct
2 Correct 13 ms 11416 KB Output is correct
3 Correct 11 ms 11416 KB Output is correct
4 Correct 15 ms 11440 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 30212 KB Output is correct
2 Correct 391 ms 30212 KB Output is correct
3 Correct 435 ms 30212 KB Output is correct
4 Correct 533 ms 31564 KB Output is correct
5 Correct 384 ms 31564 KB Output is correct
6 Correct 385 ms 31564 KB Output is correct
7 Correct 361 ms 31564 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 31564 KB Output is correct
2 Correct 225 ms 31564 KB Output is correct
3 Correct 229 ms 31564 KB Output is correct
4 Correct 255 ms 31564 KB Output is correct
5 Correct 236 ms 31564 KB Output is correct
6 Correct 273 ms 31564 KB Output is correct
7 Correct 246 ms 31564 KB Output is correct
8 Incorrect 233 ms 31564 KB Output isn't correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11260 KB Output is correct
2 Correct 13 ms 11416 KB Output is correct
3 Correct 11 ms 11416 KB Output is correct
4 Correct 15 ms 11440 KB Output is correct
5 Correct 492 ms 30212 KB Output is correct
6 Correct 391 ms 30212 KB Output is correct
7 Correct 435 ms 30212 KB Output is correct
8 Correct 533 ms 31564 KB Output is correct
9 Correct 384 ms 31564 KB Output is correct
10 Correct 385 ms 31564 KB Output is correct
11 Correct 361 ms 31564 KB Output is correct
12 Correct 174 ms 31564 KB Output is correct
13 Correct 225 ms 31564 KB Output is correct
14 Correct 229 ms 31564 KB Output is correct
15 Correct 255 ms 31564 KB Output is correct
16 Correct 236 ms 31564 KB Output is correct
17 Correct 273 ms 31564 KB Output is correct
18 Correct 246 ms 31564 KB Output is correct
19 Incorrect 233 ms 31564 KB Output isn't correct