結果

問題 No.529 帰省ラッシュ
ユーザー 小夫
提出日時 2025-03-30 22:08:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,294 bytes
コンパイル時間 2,498 ms
コンパイル使用メモリ 205,672 KB
実行使用メモリ 46,148 KB
最終ジャッジ日時 2025-03-30 22:08:26
合計ジャッジ時間 13,561 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch&15);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+48);
	return;
}
const int N=4e5+7;
int tim,dfn[N],low[N],bel[N],cnt;
vector<int>kd[N],mp[N];
priority_queue<int,vector<int>,less<int>>val[N];
stack<int>stk; 
inline void Tarjan(int x,int fa)
{
	dfn[x]=low[x]=++tim;
	stk.emplace(x);
	for(auto v:mp[x])
	{
		if(v==fa)continue;
		if(!dfn[v])
		{
			Tarjan(v,x);
			low[x]=min(low[x],low[v]);
		}
		else low[x]=min(low[x],dfn[v]);
	}
	if(low[x]==dfn[x])
	{
		int top=stk.top();
		stk.pop();
		bel[top]=++cnt;
		while(top^x)
		{
			top=stk.top();
			stk.pop();
			bel[top]=cnt;
		}
	}
	return;
}
inline bool found(int x,int fa,int pos)
{
	bool fg=0;
	for(auto g:kd[x])
	{
		if(g==fa)continue;
		if(g==pos)return true;
		fg|=found(g,x,pos);
	}
	return fg;
}
bool outl=0;
inline void dfs(int x,int fa,int pos,int&v,int&p)
{
	for(auto g:kd[x])
	{
		if(g==pos)
		{
			int k;
			if(val[g].empty())k=-1;
			else k=val[g].top();
			if(k>v)v=k,p=g;
			outl=1;
			return;
		}
		if(g==fa)continue; 
		if(!found(g,x,pos))continue;
		int k;
		if(val[g].empty())k=-1;
		else k=val[g].top();
		if(k>v)v=k,p=g;
		dfs(g,x,pos,v,p);
		if(outl)return;
	}
} 
int main()
{
	int n=read(),m=read(),q=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		mp[u].emplace_back(v);
		mp[v].emplace_back(u);
	} 
	for(int i=1;i<=n;++i)if(!dfn[i])Tarjan(i,-1);
	for(int i=1;i<=n;++i)
	{
		for(int j:mp[i])
	    	if(bel[i]^bel[j])
				kd[bel[i]].emplace_back(bel[j]);
	}
	while(q--)
	{
		int op=read();
		if(op==1)
		{
			int u=read(),w=read();
			val[bel[u]].push(w);
		}
		if(op==2)
		{
			int s=read(),t=read();
			if(bel[s]==bel[t])
			{
				if(val[bel[s]].empty()){puts("-1");continue;}
				int v=val[bel[s]].top();
				val[bel[s]].pop();
				write(v),puts("");
				continue;
			}
			else
			{
				int v,x;
				if(val[bel[s]].empty())v=-1;
				else v=val[bel[s]].top();
				x=bel[s];
				outl=0;
				dfs(bel[s],0,bel[t],v,x);
				write(v),puts("");
				if(!val[x].empty())val[x].pop();
				continue;
			}
		}
	}
    return 0;
}
0