제출 #1227998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227998		MuhammadSaram	Min-max tree (BOI18_minmaxtree)	C++20	0 / 100	124 ms	19768 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

const int M = 70001, lg = 17;

vector<int> nei[M];
// set<pair<int,int>> se[2];
vector<pair<int,int>> ad[M];
int par[M][lg],dep[M],ed[M];

void dfs(int u)
{
	for (int p=1;p<lg;p++)
		par[u][p]=par[par[u][p-1]][p-1];
	for (int i:nei[u])
		if (i!=par[u][0])
			par[i][0]=u,dep[i]=dep[u]+1,dfs(i);
}

int lca(int u,int v)
{
	if (dep[u]>dep[v]) swap(u,v);
	for (int p=lg-1;p>=0;p--)
		if (dep[v]-(1<<p)>=dep[u])
			v=par[v][p];
	if (u==v) return v;
	for (int p=lg-1;p>=0;p--)
		if (par[u][p]!=par[v][p])
			u=par[u][p],v=par[v][p];
	return par[u][0];
}

set<int> se;

void dfs1(int u)
{
	for (int i:nei[u])
		if (i!=par[u][0])
			dfs1(i);
	for (auto [x,i]:ad[u])
		if (i) se.insert(x);
	for (auto [x,i]:ad[u])
		if (!i) se.erase(x);
	if (par[u][0])
	{
		if (se.empty())
			ed[u]=0;
		else
			ed[u]=*se.begin();
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL),cout.tie(NULL);
	
	int n;
	cin>>n;
	for (int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		nei[u].push_back(v);
		nei[v].push_back(u);
	}
	dfs(1);
	int k;
	cin>>k;
	for (int i=0;i<k;i++)
	{
		char c;
		cin>>c;
		int u,v,x;
		cin>>u>>v>>x;
		int l=lca(u,v);
		ad[u].push_back({x,1});
		ad[v].push_back({x,1});
		ad[l].push_back({x,0});
	}
	dfs1(1);
	for (int i=2;i<=n;i++)
		cout<<i<<' '<<par[i][0]<<' '<<ed[i]<<endl;
	
	return 0;
}

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