제출 #1227915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227915		Muhammad_Aneeq	Min-max tree (BOI18_minmaxtree)	C++20	22 / 100	104 ms	18704 KiB

minmaxtree

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int const N=7e4+10;
vector<pair<int,int>>nei[N]={};
int P[N]={},h[N]={},vis[N]={};
void dfs(int u,int p=0)
{
	P[u]=p;
	for (auto [i,in]:nei[u])
	{
		if (i==p) continue;
		h[i]=h[u]+1;
		dfs(i,u);
	}
}
vector<vector<int>>ans;
void up(int u,int v,int val)
{
	vector<int>nd;
	while (u!=v)
	{
		if (h[u]>h[v])
		{
			nd.push_back(u);
			u=P[u];
		}
		else
		{
			nd.push_back(v);
			v=P[v];
		}
	}
	for (auto i:nd)
	{
		if (h[P[i]]==h[i]-1&&!vis[i])
		{
			vis[i]=1;
			ans.push_back({P[i],i,val});
		}
		P[i]=u;
	}
}
inline void solve()
{
	int n;
	cin>>n;
	for (int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		nei[u].push_back({v,i});
		nei[v].push_back({u,i});
	}
	dfs(1);
	int q;
	cin>>q;
	vector<vector<int>>upd;
	while (q--)
	{
		char x;
		cin>>x;
		int u,v,w;
		cin>>u>>v>>w;
		upd.push_back({w,u,v});
	}
	sort(begin(upd),end(upd));
	for (auto i:upd)
		up(i[1],i[2],i[0]);
	for (int i=2;i<=n;i++)
	{
		if (!vis[i])
			ans.push_back({i,P[i],0});
	}
	for (auto i:ans)
		cout<<i[0]<<' '<<i[1]<<' '<<i[2]<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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