oj.uz

Submission #261211

# Submission time Handle Problem Language Result Execution time Memory
261211 2020-08-11T14:40:28 Z Namnamseo Min-max tree (BOI18_minmaxtree) C++17
100 / 100
 513 ms 43148 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void cppio(){ ios_base::sync_with_stdio(0); cin.tie(0); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define sz(x) (int)(x).size()

const int maxn = 70010;
vector<int> cond[maxn];
vector<int> delh[maxn];
vector<int> e[maxn];

int n;
int par[17][maxn];
int dep[maxn];

void dfs(int x){ for(int y:e[x]) if(par[0][x] != y){ par[0][y] = x; dep[y]=dep[x]+1; dfs(y); } }
int lca(int a, int b){
	if(dep[a] > dep[b]) swap(a, b);
	for(int i=16; 0<=i; --i) if(1&((dep[b]-dep[a])>>i)) b=par[i][b];
	if(a==b) return a;
	for(int i=16; 0<=i; --i) if(par[i][a] != par[i][b]) a=par[i][a], b=par[i][b];
	return par[0][a];
}

int ct[maxn];
int cv[maxn];
pp pe[maxn];

multiset<int> lb[maxn], ub[maxn];

void solve(int x){
	auto &L=lb[x], &U=ub[x];
	for(int y:e[x]) if(par[0][y] == x){
		solve(y);
		if(L.size()+U.size() < lb[y].size()+ub[y].size()){
			swap(L, lb[y]);
			swap(U, ub[y]);
		}
		L.insert(all(lb[y])); lb[y].clear();
		U.insert(all(ub[y])); ub[y].clear();
	}

	for(int c:cond[x]){
		if(ct[c] == 0) L.insert(cv[c]);
		else U.insert(cv[c]);
	}

	pe[x] = {-1, -1};
	if(L.size()) pe[x].x = *--L.end();
	if(U.size()) pe[x].y = *U.begin();

	for(int c:delh[x]){
		if(ct[c] == 0) L.erase(L.find(cv[c]));
		else U.erase(U.find(cv[c]));
	}
}

namespace match {
	const int maxv = 70000 * 2 + 10;
	vector<int> e[maxv];
	int lev[maxv];
	int rev[maxv];
	int mat[maxv];

	void adde(int l, int r){
		e[l].pb(r);
	}

	void match(int n, int m){
	auto bfs = [&](){
		fill(lev+1, lev+n+m+1, -1);
		queue<int> q;
		rrep(i, n) if(!mat[i]){ lev[i]=0; q.push(i); }
		bool reach = 0;
		while(q.size()){
			int x=q.front(); q.pop();
			if(x > n){
				if(rev[x]){ lev[rev[x]] = lev[x]+1; q.push(rev[x]); }
				else reach = 1;
			} else for(int y:e[x]) if(!~lev[y]){
				lev[y] = lev[x]+1; q.push(y);
			}
		}
		return reach;
	};

		static bool vis[maxv];
	function<bool(int)> dfs = [&](int x){
		if(vis[x]) return 0;
		vis[x]=1;
		for(int y:e[x]) if(lev[y]==lev[x]+1){
			if(!rev[y]){
				rev[y]=x; mat[x]=y;
				return 1;
			} else if(lev[rev[y]] == lev[y]+1){
				if(dfs(rev[y])){
					rev[y]=x; mat[x]=y;
					return 1;
				}
			}
		}
		return 0;
	};

		while(bfs()){
			fill(vis+1, vis+n+1, 0);
			rrep(i, n) if(lev[i]==0 && !vis[i]) dfs(i);
		}
	}
};

map<int,int> rm;

int kp(int x, int k){
	for(int i=16; 0<=i; --i) if(1&(k>>i)) x=par[i][x];
	return x;
}

int main()
{
	int k;
[&](){
	cppio(); cin >> n;
	rep(i, n-1){ int a, b; cin >> a >> b; e[a].pb(b); e[b].pb(a); }

	dfs(1);
	rrep(i, 16) rrep(j, n) par[i][j] = par[i-1][par[i-1][j]];

	cin >> k;
	rrep(i, k){
		char cmd[5];
		int x, y, z;
		cin >> cmd >> x >> y >> z;
		int l = lca(x, y);
		if(l != x) cond[x].pb(i), delh[kp(x, dep[x]-dep[l]-1)].pb(i);
		if(l != y) cond[y].pb(i), delh[kp(y, dep[y]-dep[l]-1)].pb(i);

		ct[i] = (cmd[0] == 'M');
		cv[i] = z;

		rm[z] = i;
	}
}();

	solve(1);
	rrep(i, n) if(par[0][i]){
		int x, y; tie(x, y) = pe[i];
		if(~x) match::adde(rm[x], k+i);
		if(~y) match::adde(rm[y], k+i);
	}

	match::match(k, n);

	rrep(i, n) if(par[0][i]){
		int j = par[0][i];
		printf("%d %d ", i, j);
		if(match::rev[k+i]){
			printf("%d\n", cv[match::rev[k+i]]);
		} else {
			int a, b; tie(a, b) = pe[i];
			if(a != -1) printf("%d\n", a);
			else if(b != -1) printf("%d\n", b);
			else puts("1");
		}
	}

	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15232 KB Output is correct
2 Correct 12 ms 15232 KB Output is correct
3 Correct 12 ms 15232 KB Output is correct
4 Correct 13 ms 15232 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 41040 KB Output is correct
2 Correct 410 ms 37340 KB Output is correct
3 Correct 410 ms 38136 KB Output is correct
4 Correct 402 ms 41424 KB Output is correct
5 Correct 396 ms 37664 KB Output is correct
6 Correct 359 ms 37972 KB Output is correct
7 Correct 339 ms 37972 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 31148 KB Output is correct
2 Correct 232 ms 31276 KB Output is correct
3 Correct 189 ms 32984 KB Output is correct
4 Correct 221 ms 34520 KB Output is correct
5 Correct 238 ms 31756 KB Output is correct
6 Correct 220 ms 32384 KB Output is correct
7 Correct 206 ms 31240 KB Output is correct
8 Correct 224 ms 31116 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15232 KB Output is correct
2 Correct 12 ms 15232 KB Output is correct
3 Correct 12 ms 15232 KB Output is correct
4 Correct 13 ms 15232 KB Output is correct
5 Correct 394 ms 41040 KB Output is correct
6 Correct 410 ms 37340 KB Output is correct
7 Correct 410 ms 38136 KB Output is correct
8 Correct 402 ms 41424 KB Output is correct
9 Correct 396 ms 37664 KB Output is correct
10 Correct 359 ms 37972 KB Output is correct
11 Correct 339 ms 37972 KB Output is correct
12 Correct 212 ms 31148 KB Output is correct
13 Correct 232 ms 31276 KB Output is correct
14 Correct 189 ms 32984 KB Output is correct
15 Correct 221 ms 34520 KB Output is correct
16 Correct 238 ms 31756 KB Output is correct
17 Correct 220 ms 32384 KB Output is correct
18 Correct 206 ms 31240 KB Output is correct
19 Correct 224 ms 31116 KB Output is correct
20 Correct 462 ms 37472 KB Output is correct
21 Correct 395 ms 36068 KB Output is correct
22 Correct 387 ms 35880 KB Output is correct
23 Correct 370 ms 35320 KB Output is correct
24 Correct 445 ms 41480 KB Output is correct
25 Correct 450 ms 43148 KB Output is correct
26 Correct 406 ms 41508 KB Output is correct
27 Correct 484 ms 40456 KB Output is correct
28 Correct 418 ms 38052 KB Output is correct
29 Correct 442 ms 38308 KB Output is correct
30 Correct 438 ms 36064 KB Output is correct
31 Correct 477 ms 36040 KB Output is correct
32 Correct 513 ms 37676 KB Output is correct
33 Correct 477 ms 36416 KB Output is correct
34 Correct 447 ms 36292 KB Output is correct
35 Correct 396 ms 35656 KB Output is correct