Submission #380706

#	Time	Username	Problem	Language	Result	Execution time	Memory
380706		VodkaInTheJar	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	299 ms	27876 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 + 3; 

struct chain
{
	int a, b, w; 
	chain() {}
	chain(int a, int b, int w)
	{
		this->a = a;
		this->b = b;
		this->w = w; 
	}
	
	bool operator < (const chain &other) const
	{
		return w < other.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 = -1;}
};

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();
	sort (vmin.begin(), vmin.end());
	sort (vmax.begin(), vmax.end());
	
	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 = 2; i <= n; i++)
	{
		int idx1 = lower_bound(vmin.begin(), vmin.end(), chain(0, 0, l[i])) - vmin.begin();
		int idx2 = lower_bound(vmax.begin(), vmax.end(), chain(0, 0, r[i])) - vmax.begin();
		
		if (l[i] != -1)
		adj1[i].push_back(idx1 + 1);
		
		if (r[i] != inf)
		adj1[i].push_back(idx2 + (int)vmin.size() + 1);
	}
	
	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;
	}
	
	for (int i = 2; i <= n; i++)
	if (ans[i] == -1)
	ans[i] = l[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: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42