oj.uz

Submission #91887

# Submission time Handle Problem Language Result Execution time Memory
91887 2018-12-31T08:58:20 Z tmwilliamlin168 Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 495 ms 32392 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=7e4;
int n, ui, vi, d[mxN], anc[mxN][17], c1[mxN][17], c2[mxN][17], k, wi, i2w[mxN], mt[mxN-1];
vector<int> adj[mxN], cm[mxN];
char qt;
unordered_map<int, int> w2i;
bool vis[mxN];

void dfs1(int u=n-1, int p=-1) {
	anc[u][0]=p;
	for(int i=1; i<17; ++i)
		anc[u][i]=anc[u][i-1]==-1?-1:anc[anc[u][i-1]][i-1];
	d[u]=p==-1?0:d[p]+1;
	for(int v : adj[u])
		if(v!=p)
			dfs1(v, u);
}

bool dfs2(int u) {
	vis[u]=1;
	for(int v : cm[u]) {
		if(mt[v]==-1||!vis[mt[v]]&&dfs2(mt[v])) {
			mt[v]=u;
			return 1;
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for(int i=0; i<n-1; ++i) {
		cin >> ui >> vi, --ui, --vi;
		adj[ui].push_back(vi);
		adj[vi].push_back(ui);
	}
	dfs1();
	memset(c2, 0x96, sizeof(c2));
	cin >> k;
	for(int i=0; i<k; ++i) {
		cin >> qt >> ui >> vi >> wi, --ui, --vi;
		i2w[i]=wi;
		w2i[wi]=i;
		int (*c)[17];
		if(qt=='M') {
			wi=-wi;
			c=c2;
		} else
			c=c1;
		if(d[ui]<d[vi])
			swap(ui, vi);
		auto ue=[&](int &u, int j) {
			c[u][j]=max(wi, c[u][j]);
			u=anc[u][j];
		};
		for(int j=16; j>=0; --j)
			if(d[ui]-(1<<j)>=d[vi])
				ue(ui, j);
		if(ui!=vi) {
			for(int j=16; j>=0; --j) {
				if(anc[ui][j]!=anc[vi][j]) {
					ue(ui, j);
					ue(vi, j);
				}
			}
			ue(ui, 0);
			ue(vi, 0);
		}
	}
	for(int i=16; i; --i) {
		for(int j=0; j<n; ++j) {
			c1[j][i-1]=max(c1[j][i], c1[j][i-1]);
			c2[j][i-1]=max(c2[j][i], c2[j][i-1]);
			if(anc[j][i-1]!=-1) {
				c1[anc[j][i-1]][i-1]=max(c1[j][i], c1[anc[j][i-1]][i-1]);
				c2[anc[j][i-1]][i-1]=max(c2[j][i], c2[anc[j][i-1]][i-1]);
			}
		}
	}
	for(int i=0; i<n-1; ++i) {
		c2[i][0]=-c2[i][0];
		if(w2i.find(c1[i][0])!=w2i.end())
			cm[w2i[c1[i][0]]].push_back(i);
		if(w2i.find(c2[i][0])!=w2i.end())
			cm[w2i[c2[i][0]]].push_back(i);
	}
	memset(mt, -1, 4*(n-1));
	for(int i=0; i<k; ++i) {
		dfs2(i);
		memset(vis, 0, k);
	}
	for(int i=0; i<n-1; ++i)
		cout << i+1 << " " << anc[i][0]+1 << " " << (mt[i]>=0&&i2w[mt[i]]==c1[i][0]?c1[i][0]:c2[i][0]) << "\n";
}

Compilation message

minmaxtree.cpp: In function 'bool dfs2(int)':
minmaxtree.cpp:24:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(mt[v]==-1||!vis[mt[v]]&&dfs2(mt[v])) {
                 ~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8312 KB Output is correct
2 Correct 7 ms 8312 KB Output is correct
3 Correct 7 ms 8312 KB Output is correct
4 Correct 7 ms 8312 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 29008 KB Output is correct
2 Correct 429 ms 27400 KB Output is correct
3 Correct 356 ms 28168 KB Output is correct
4 Correct 453 ms 29448 KB Output is correct
5 Correct 400 ms 27780 KB Output is correct
6 Correct 467 ms 28040 KB Output is correct
7 Correct 405 ms 27392 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 23800 KB Output is correct
2 Correct 122 ms 25208 KB Output is correct
3 Correct 161 ms 27356 KB Output is correct
4 Correct 158 ms 27612 KB Output is correct
5 Correct 143 ms 25464 KB Output is correct
6 Correct 156 ms 25896 KB Output is correct
7 Correct 156 ms 25640 KB Output is correct
8 Correct 145 ms 25556 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8312 KB Output is correct
2 Correct 7 ms 8312 KB Output is correct
3 Correct 7 ms 8312 KB Output is correct
4 Correct 7 ms 8312 KB Output is correct
5 Correct 400 ms 29008 KB Output is correct
6 Correct 429 ms 27400 KB Output is correct
7 Correct 356 ms 28168 KB Output is correct
8 Correct 453 ms 29448 KB Output is correct
9 Correct 400 ms 27780 KB Output is correct
10 Correct 467 ms 28040 KB Output is correct
11 Correct 405 ms 27392 KB Output is correct
12 Correct 126 ms 23800 KB Output is correct
13 Correct 122 ms 25208 KB Output is correct
14 Correct 161 ms 27356 KB Output is correct
15 Correct 158 ms 27612 KB Output is correct
16 Correct 143 ms 25464 KB Output is correct
17 Correct 156 ms 25896 KB Output is correct
18 Correct 156 ms 25640 KB Output is correct
19 Correct 145 ms 25556 KB Output is correct
20 Correct 425 ms 29684 KB Output is correct
21 Correct 294 ms 28424 KB Output is correct
22 Correct 325 ms 28552 KB Output is correct
23 Correct 353 ms 28680 KB Output is correct
24 Correct 495 ms 31620 KB Output is correct
25 Correct 397 ms 32072 KB Output is correct
26 Correct 373 ms 31560 KB Output is correct
27 Correct 418 ms 32392 KB Output is correct
28 Correct 482 ms 30088 KB Output is correct
29 Correct 453 ms 30232 KB Output is correct
30 Correct 403 ms 28992 KB Output is correct
31 Correct 410 ms 28932 KB Output is correct
32 Correct 461 ms 29944 KB Output is correct
33 Correct 401 ms 29316 KB Output is correct
34 Correct 346 ms 29180 KB Output is correct
35 Correct 370 ms 28852 KB Output is correct