Submission #380677

#	Time	Username	Problem	Language	Result	Execution time	Memory
380677		VodkaInTheJar	Min-max tree (BOI18_minmaxtree)	C++14	7 / 100	1092 ms	21984 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];
bool used[maxn];

bool kuhn(int ver)
{
	for (auto i: adj1[ver])
	if (!used[i])
	{
		used[i] = true; 
		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++)
	{
		for (int j = 0; j < (int)vmin.size(); j++)
		{
			if (vmin[j].w > r[i] || vmin[j].w < l[i])
			continue;
			
			int cnt = 0;
			if (is_upper(i, vmin[j].a))
			cnt++;
			
			if (is_upper(i, vmin[j].b))
			cnt++;
			
			if (cnt == 1)
			adj1[i].push_back(j + 1);
		}
		
		for (int j = 0; j < (int)vmax.size(); j++)
		{
			if (vmax[j].w > r[i] || vmax[j].w < l[i])
			continue;
			
			int cnt = 0;
			if (is_upper(i, vmax[j].a))
			cnt++;
			
			if (is_upper(i, vmax[j].b))
			cnt++;
			
			if (cnt == 1)
			adj1[i].push_back(j + (int)vmin.size() + 1);
		}
	}
	
	for (int i = 1; i <= k; i++)
	match[i] = -1; 
	
	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j <= k; j++)
		used[j] = false;
		
		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: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42