제출 #380697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380697		VodkaInTheJar	Min-max tree (BOI18_minmaxtree)	C++14	0 / 100	253 ms	21396 KiB

minmaxtree

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

const int maxn = 70003; 
const int maxlog = 20; 
const int inf = 1e9; 

struct chain
{
	int a, b, w; 
	chain() {}
	chain(int a, int b, int w)
	{
		this->a = a;
		this->b = b;
		this->w = w; 
	}
};

int n, k;
vector <int> adj[maxn];
vector <chain> vmin, vmax;

void read()
{
	cin >> n;
	for (int i = 1; i <= n-1; i++)
	{
		int a, b;
		cin >> a >> b;
		
		adj[a].push_back(b);
		adj[b].push_back(a);
	}	
	
	cin >> k;
	for (int i = 1; i <= k; i++)
	{
		char type;
		int a, b, w;
		cin >> type >> a >> b >> w;
		
		if (type == 'm')
		vmin.push_back(chain(a, b, w));
		
		else 
		vmax.push_back(chain(a, b, w));
	}
}

int sz[maxn];
int par[maxn][maxlog];


void pre_dfs(int ver)
{
	sz[ver] = 1;
	
	for (auto i: adj[ver])
	if (i != par[ver][0])
	{
		par[i][0] = ver;
		pre_dfs(i);
	    sz[ver] += sz[i];
	}
}

int pos[maxn], head[maxn];
vector <int> order;

void dfs(int ver, int curr_head)
{
	order.push_back(ver);
	pos[ver] = (int)order.size()-1; 
	head[ver] = curr_head;
	
	int max_sz = -1, idx = -1;
	for (auto i: adj[ver])
	if (i != par[ver][0])
	if (sz[i] > max_sz)
	max_sz = sz[i], idx = i;
	
	if (idx != -1)
	dfs(idx, curr_head);
	
	for (auto i: adj[ver])
	if (i != par[ver][0] && i != idx)
	dfs(i, i);
}

void precompute()
{
	pre_dfs(1);
	dfs(1, 1);
	
	for (int j = 1; j < maxlog; j++)
	for (int i = 1; i <= n; i++)
	par[i][j] = par[par[i][j-1]][j-1];
}

bool is_upper(int a, int b)
{
	return pos[a] <= pos[b] && pos[a] + sz[a] - 1 >= pos[b];
}

int lca(int a, int b)
{
	if (is_upper(a, b))
	return a;
	
	for (int i = maxlog-1; i >= 0; i--)
	if (par[a][i] && !is_upper(par[a][i], b))
	a = par[a][i];
	
	return par[a][0];
}

struct node
{
	int min_val, max_val;
	node() {min_val = inf, max_val = 0;}
};

node tr[maxn * 4];
void update(int v, int l, int r, int ll, int rr, int val, bool type)
{
	if (l > rr || r < ll)
	return;
	
	if (l >= ll && r <= rr)
	{
		if (type)
		tr[v].min_val = min(tr[v].min_val, val);
		
		else 
		tr[v].max_val = max(tr[v].max_val, val);
		
		return;
	}
	
	int mid = (l + r) / 2;
	update(v * 2, l, mid, ll, rr, val, type);
	update(v * 2 + 1, mid + 1, r, ll, rr, val, type);
}

int get_min(int v, int l, int r, int pos)
{
	if (l == r)
	return tr[v].min_val;
	
	int mid = (l + r) / 2;
	if (pos <= mid)
	return min(tr[v].min_val, get_min(v * 2, l, mid, pos));
	
	else 
	return min(tr[v].min_val, get_min(v * 2 + 1, mid + 1, r, pos));
}

int get_max(int v, int l, int r, int pos)
{
	if (l == r)
	return tr[v].max_val;
	
	int mid = (l + r) / 2;
	if (pos <= mid)
	return max(tr[v].max_val, get_max(v * 2, l, mid, pos));
	
	else 
	return max(tr[v].max_val, get_max(v * 2 + 1, mid + 1, r, pos));
}

void update_min(int a, int b, int w)
{
	if (a == b)
	return;
	
	while (!is_upper(head[a], b))
	{
		update(1, 0, n-1, pos[head[a]], pos[a], w, true);
		a = par[head[a]][0];
	}
	
	update(1, 0, n-1, pos[b]+1, pos[a], w, true);
}

void update_max(int a, int b, int w)
{
	if (a == b)
	return;
	
	while (!is_upper(head[a], b))
	{
		update(1, 0, n-1, pos[head[a]], pos[a], w, false);
		a = par[head[a]][0];
	}
	
	update(1, 0, n-1, pos[b]+1, pos[a], w, false);
}

int l[maxn], r[maxn];

vector <int> adj1[maxn];
int match[maxn];
int used[maxn];
int curr_time;

bool kuhn(int ver)
{
	for (auto i: adj1[ver])
	if (used[i] != curr_time)
	{
		used[i] = curr_time; 
		if (match[i] == -1 || kuhn(match[i]))
		{
			match[i] = ver;
			return true; 
		}
	}
	
	return false;
}

int ans[maxn];
void solve()
{
	precompute();
	
	for (auto i: vmin)
	{
		int curr_lca = lca(i.a, i.b);
		update_max(i.a, curr_lca, i.w);
		update_max(i.b, curr_lca, i.w);
	}
	
	for (auto i: vmax)
	{
		int curr_lca = lca(i.a, i.b);
		update_min(i.a, curr_lca, i.w);
		update_min(i.b, curr_lca, i.w);
	}
	
	for (int i = 2; i <= n; i++)
	{
		l[i] = get_max(1, 0, n-1, pos[i]);
		r[i] = get_min(1, 0, n-1, pos[i]);
	}
	
	/*
	for (int i = 0; i < (int)vmin.size(); i++)
	{
		int c = lca(vmin[i].a, vmin[i].b);
		int curr = vmin[i].a;
		while (curr != c)
		{
			if (vmin[i].w >= l[curr] && vmin[i].w <= r[curr])
			adj1[curr].push_back(i + 1);
				
			curr = par[curr][0];
		}
		
		curr = vmin[i].b;
		while (curr != c)
		{
			if (vmin[i].w >= l[curr] && vmin[i].w <= r[curr])
			adj1[curr].push_back(i + 1);
				
			curr = par[curr][0];
		}
	}
	
	for (int i = 0; i < (int)vmax.size(); i++)
	{
		int c = lca(vmax[i].a, vmax[i].b);
		int curr = vmax[i].a;
		while (curr != c)
		{
			if (vmax[i].w >= l[curr] && vmax[i].w <= r[curr])
			adj1[curr].push_back(i + 1 + (int)vmin.size());
				
			curr = par[curr][0];
		}
		
		curr = vmax[i].b;
		while (curr != c)
		{
			if (vmax[i].w >= l[curr] && vmax[i].w <= r[curr])
			adj1[curr].push_back(i + 1 + (int)vmin.size());
				
			curr = par[curr][0];
		}
	}
	
	memset(match, -1, sizeof(match));
	memset(used, -1, sizeof(match));
	
	for (int i = 2; i <= n; i++)
	{
		curr_time++;
		kuhn(i);
	}
	
	memset(ans, -1, sizeof(ans));
	for (int i = 1; i <= k; i++)
	{
		if (i <= (int)vmin.size())
		ans[match[i]] = vmin[i-1].w;
		
		else 
		ans[match[i]] = vmax[i-(int)vmin.size()-1].w;
	}
	*/
	
	memset(ans, -1, sizeof(ans));
	
	for (auto i: vmax)
	{
		int c = lca(i.a, i.b);
		vector <int> v;
		
		int curr = i.a;
		while (curr != c)
		{
			v.push_back(curr);
			curr = par[curr][0];
		}
		
		curr = i.b;
		while (curr != c)
		{
			v.push_back(curr);
			curr = par[curr][0];
		}
		
		int max_low = -1; 
		for (auto j: v)
		if (r[j] == i.w && ans[j] == -1)
		max_low = max(max_low, l[j]);
		
		for (auto j: v)
		if (l[j] == max_low && ans[j] == -1)
		{
			ans[j] = i.w;
			break;
		}
	}
	
	for (auto i: vmin)
	{
		int c = lca(i.a, i.b);
		vector <int> v;
		
		int curr = i.a;
		while (curr != c)
		{
			v.push_back(curr);
			curr = par[curr][0];
		}
		
		curr = i.b;
		while (curr != c)
		{
			v.push_back(curr);
			curr = par[curr][0];
		}
		
		int min_high = inf; 
		for (auto j: v)
		if (l[j] == i.w && ans[j] == -1)
		min_high = min(min_high, r[j]);
		
		for (auto j: v)
		if (r[j] == min_high && ans[j] == -1)
		{
			ans[j] = i.w;
			break;
		}
	}
	
	for (int i = 2; i <= n; i++)
	if (ans[i] == -1)
	ans[i] = r[i];
	
	for (int i = 2; i <= n; i++)
	cout << i << " " << par[i][0] << " " << ans[i] << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	read();
	solve();
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42