답안 #71914 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71914	2018-08-25T20:48:35 Z	Good	Min-max tree (BOI18_minmaxtree)	C++11	29 / 100	482 ms	31592 KB

minmaxtree

#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

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

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

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

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

답안 #71914

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