답안 #72620 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72620	2018-08-26T12:00:57 Z	Good	Min-max tree (BOI18_minmaxtree)	C++11	29 / 100	533 ms	31564 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 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #72620

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