답안 #72619 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72619	2018-08-26T11:59:22 Z	Good	Min-max tree (BOI18_minmaxtree)	C++11	29 / 100	517 ms	47120 KB

minmaxtree

#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 (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 {
				if (E[i][0] == -1 and E[i][1] != -1)
					assert (1);
					
				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

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	11256 KB	Output is correct
2	Correct	12 ms	11336 KB	Output is correct
3	Correct	13 ms	11408 KB	Output is correct
4	Correct	12 ms	11452 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	517 ms	32584 KB	Output is correct
2	Correct	500 ms	32584 KB	Output is correct
3	Correct	468 ms	33752 KB	Output is correct
4	Correct	420 ms	40856 KB	Output is correct
5	Correct	512 ms	40856 KB	Output is correct
6	Correct	451 ms	40856 KB	Output is correct
7	Correct	473 ms	41308 KB	Output is correct

Subtask #3
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	219 ms	41308 KB	Output is correct
2	Correct	296 ms	41308 KB	Output is correct
3	Correct	262 ms	43564 KB	Output is correct
4	Correct	236 ms	47120 KB	Output is correct
5	Correct	267 ms	47120 KB	Output is correct
6	Correct	228 ms	47120 KB	Output is correct
7	Correct	247 ms	47120 KB	Output is correct
8	Incorrect	262 ms	47120 KB	Output isn't correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	11256 KB	Output is correct
2	Correct	12 ms	11336 KB	Output is correct
3	Correct	13 ms	11408 KB	Output is correct
4	Correct	12 ms	11452 KB	Output is correct
5	Correct	517 ms	32584 KB	Output is correct
6	Correct	500 ms	32584 KB	Output is correct
7	Correct	468 ms	33752 KB	Output is correct
8	Correct	420 ms	40856 KB	Output is correct
9	Correct	512 ms	40856 KB	Output is correct
10	Correct	451 ms	40856 KB	Output is correct
11	Correct	473 ms	41308 KB	Output is correct
12	Correct	219 ms	41308 KB	Output is correct
13	Correct	296 ms	41308 KB	Output is correct
14	Correct	262 ms	43564 KB	Output is correct
15	Correct	236 ms	47120 KB	Output is correct
16	Correct	267 ms	47120 KB	Output is correct
17	Correct	228 ms	47120 KB	Output is correct
18	Correct	247 ms	47120 KB	Output is correct
19	Incorrect	262 ms	47120 KB	Output isn't correct

답안 #72619

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 22.0 / 22.0

Subtask #3 0 / 29.0

Subtask #4 0 / 42.0

Subtask #1
7.0 / 7.0

Subtask #2
22.0 / 22.0

Subtask #3
0 / 29.0

Subtask #4
0 / 42.0