답안 #61491 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61491	2018-07-26T05:32:46 Z	윤교준(#1780)	Min-max tree (BOI18_minmaxtree)	C++11	100 / 100	293 ms	18252 KB

minmaxtree

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }

const bool debug = 0;
const int MAXN = 70005;
const int MAXK = 70005;

vector<int> G[MAXN];
int F[MAXK];

int prt[17][MAXN], dep[MAXN];
int dpmx[MAXN], dpmn[MAXN];
int dpmxi[MAXN], dpmni[MAXN];
vector<int> XV;

int ud[MAXN];
int chk[MAXN], chkn;

int A[MAXN], B[MAXN];
int C[MAXK], D[MAXK], E[MAXK];
bitset<MAXK> isM;

int Ans[MAXN];
int N, K;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	const int dt = dep[b] - dep[a];
	for(int i = 0; i < 17; i++) if(dt & (1<<i))
		b = prt[i][b];
	if(a == b) return a;
	for(int i = 17; i--;) if(prt[i][a] != prt[i][b]) {
		a = prt[i][a]; b = prt[i][b];
	}
	return prt[0][a];
}

void dfs(int i) {
	for(int v : G[i]) if(!dep[v]) {
		dep[v] = dep[i] + 1;
		prt[0][v] = i;
		dfs(v);
	}
}

void f(int d[], int a, int b, int c) {
	for(;;) {
		a = uf(a);
		if(dep[a] <= dep[b]) break;
		d[a] = c;
		uf(prt[0][a], a);
	}
}

bool g(int i) {
	if(chk[i] == chkn) return false;
	chk[i] = chkn;
	for(int v : G[i]) if(!F[v] || g(F[v]))
		return F[v] = i;
	return false;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i < N; i++) {
		cin >> A[i] >> B[i];
		fg(G, A[i], B[i]);
	}
	cin >> K;
	for(int i = 1; i <= K; i++) {
		char c;
		cin >> c >> C[i] >> D[i] >> E[i];
		isM[i] = ('M' == c);
	}

	dep[1] = 1; dfs(1);
	for(int j = 1; j < 17; j++) for(int i = 1; i <= N; i++)
		prt[j][i] = prt[j-1][prt[j-1][i]];
	for(int i = 1; i < N; i++) if(dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
	
	{
		vector<pair<int, pii>> EV;
		for(int i = 1, a, b, c, t; i <= K; i++) if(isM[i]) {
			a = C[i]; b = D[i]; c = E[i];
			t = lca(a, b);
			if(t != a) EV.eb(c, pii(a, t));
			if(t != b) EV.eb(c, pii(b, t));
		}
		fill(dpmx, dpmx+N+1, INF);
		iota(ud, ud+N+1, 0);
		sorv(EV);
		for(auto &e : EV) f(dpmx, e.second.first, e.second.second, e.first);
	}
	{
		vector<pair<int, pii>> EV;
		for(int i = 1, a, b, c, t; i <= K; i++) if(!isM[i]) {
			a = C[i]; b = D[i]; c = E[i];
			t = lca(a, b);
			if(t != a) EV.eb(-c, pii(a, t));
			if(t != b) EV.eb(-c, pii(b, t));
		}
		fill(dpmn, dpmn+N+1, -INF);
		iota(ud, ud+N+1, 0);
		sorv(EV);
		for(auto &e : EV) f(dpmn, e.second.first, e.second.second, -e.first);
	}
	
	if(debug) {
		for(int i = 1; i <= N; i++)
			printf("%d : %d %d :: %d %d\n", i, prt[0][i], dep[i], dpmx[i], dpmn[i]);
	}

	for(int i = 1; i <= K; i++) XV.eb(E[i]);
	XV.eb(INF); XV.eb(-INF);
	sorv(XV);
	for(int i = 2; i <= N; i++) {
		dpmxi[i] = INF == dpmx[i] ? -1 : int(lower_bound(allv(XV), dpmx[i]) - XV.begin());
		dpmni[i] = -INF == dpmn[i] ? -1 : int(lower_bound(allv(XV), dpmn[i]) - XV.begin());
	}
	
	for(int i = 1; i <= N; i++) G[i].clear();
	for(int i = 2; i <= N; i++) {
		if(0 <= dpmxi[i]) G[i].eb(dpmxi[i]);
		if(0 <= dpmni[i]) G[i].eb(dpmni[i]);
	}

	for(int i = 2; i <= N; i++) { chkn++; g(i); }

	if(debug) {
		for(int i = 0; i < sz(XV); i++)
			printf("%d ; %d / %d\n", i, XV[i], F[i]);
	}

	fill(Ans, Ans+N+1, -1);
	for(int i = 0; i < sz(XV); i++) {
		int t = F[i]; if(!t) continue;
		Ans[t] = XV[i];
	}
	for(int i = 2; i <= N; i++)
		if(Ans[i] < 0) Ans[i] = dpmx[i];

	for(int i = 1; i < N; i++)
		printf("%d %d %d\n", A[i], B[i], Ans[B[i]]);
	return 0;
}

Compilation message

minmaxtree.cpp: In function 'bool g(int)':
minmaxtree.cpp:78:15: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   return F[v] = i;
          ~~~~~^~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2168 KB	Output is correct
2	Correct	5 ms	2168 KB	Output is correct
3	Correct	4 ms	2204 KB	Output is correct
4	Correct	4 ms	2228 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	192 ms	16920 KB	Output is correct
2	Correct	178 ms	16920 KB	Output is correct
3	Correct	247 ms	16920 KB	Output is correct
4	Correct	195 ms	17512 KB	Output is correct
5	Correct	190 ms	17512 KB	Output is correct
6	Correct	190 ms	17512 KB	Output is correct
7	Correct	213 ms	17512 KB	Output is correct

Subtask #3
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	175 ms	17512 KB	Output is correct
2	Correct	182 ms	17512 KB	Output is correct
3	Correct	155 ms	17512 KB	Output is correct
4	Correct	159 ms	17512 KB	Output is correct
5	Correct	185 ms	17512 KB	Output is correct
6	Correct	194 ms	17512 KB	Output is correct
7	Correct	146 ms	17512 KB	Output is correct
8	Correct	178 ms	17512 KB	Output is correct

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2168 KB	Output is correct
2	Correct	5 ms	2168 KB	Output is correct
3	Correct	4 ms	2204 KB	Output is correct
4	Correct	4 ms	2228 KB	Output is correct
5	Correct	192 ms	16920 KB	Output is correct
6	Correct	178 ms	16920 KB	Output is correct
7	Correct	247 ms	16920 KB	Output is correct
8	Correct	195 ms	17512 KB	Output is correct
9	Correct	190 ms	17512 KB	Output is correct
10	Correct	190 ms	17512 KB	Output is correct
11	Correct	213 ms	17512 KB	Output is correct
12	Correct	175 ms	17512 KB	Output is correct
13	Correct	182 ms	17512 KB	Output is correct
14	Correct	155 ms	17512 KB	Output is correct
15	Correct	159 ms	17512 KB	Output is correct
16	Correct	185 ms	17512 KB	Output is correct
17	Correct	194 ms	17512 KB	Output is correct
18	Correct	146 ms	17512 KB	Output is correct
19	Correct	178 ms	17512 KB	Output is correct
20	Correct	228 ms	17512 KB	Output is correct
21	Correct	227 ms	17512 KB	Output is correct
22	Correct	258 ms	17512 KB	Output is correct
23	Correct	208 ms	17512 KB	Output is correct
24	Correct	270 ms	17516 KB	Output is correct
25	Correct	268 ms	18252 KB	Output is correct
26	Correct	224 ms	18252 KB	Output is correct
27	Correct	293 ms	18252 KB	Output is correct
28	Correct	204 ms	18252 KB	Output is correct
29	Correct	209 ms	18252 KB	Output is correct
30	Correct	227 ms	18252 KB	Output is correct
31	Correct	220 ms	18252 KB	Output is correct
32	Correct	248 ms	18252 KB	Output is correct
33	Correct	206 ms	18252 KB	Output is correct
34	Correct	246 ms	18252 KB	Output is correct
35	Correct	198 ms	18252 KB	Output is correct

답안 #61491

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 22.0 / 22.0

Subtask #3 29.0 / 29.0

Subtask #4 42.0 / 42.0

Subtask #1
7.0 / 7.0

Subtask #2
22.0 / 22.0

Subtask #3
29.0 / 29.0

Subtask #4
42.0 / 42.0