結果

問題 No.529 帰省ラッシュ
ユーザー 小夫
提出日時 2025-03-30 20:28:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,678 bytes
コンパイル時間 2,750 ms
コンパイル使用メモリ 207,204 KB
実行使用メモリ 813,768 KB
最終ジャッジ日時 2025-03-30 20:28:48
合計ジャッジ時間 8,178 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 MLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

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=5e4+7;
struct edge{int nxt,to;}edge[N];
int hd[N],tot;
inline void addedge(int u,int v)
{
	edge[++tot].to=v;
	edge[tot].nxt=hd[u];
	hd[u]=tot;
}
int tim,dfn[N],low[N],bel[N],cnt,M;
vector<int>kd[N],ld[N];
//vector<vector<int>>kd,ld; 
priority_queue<int,vector<int>,less<int>>val[N];
inline void Tarjan(int x,int fa)
{
	dfn[x]=low[x]=++tim;
	kd[x].push_back(x);
	for(int i=hd[x];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(v==fa)continue;
		if(!low[v])
		{
			Tarjan(v,x);
			for(auto s:kd[v])kd[x].emplace_back(s);
		}
		low[x]=min(low[x],low[v]);
	}
	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(!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()
{
//	freopen("visit.in","r",stdin);
//	freopen("visit.out","w",stdout);
	int n=read(),m=read(),q=read();M=n;
//	kd.resize(n),ld.resize(n);
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
		ld[u].emplace_back(v);
		ld[v].emplace_back(u);
	} 
	Tarjan(1,0);
	for(int i=1;i<=n;++i)
		if(dfn[i]==low[i])
		{
			++cnt;
			for(auto s:kd[i])bel[s]=cnt;
		}
	for(int i=1;i<=n;++i)kd[i].clear();
//	kd.resize(cnt);
	for(int i=1;i<=n;++i)for(auto s:ld[i])if(s^bel[i])kd[bel[i]].emplace_back(bel[s]);
	for(int i=1;i<=cnt;++i)
	{
		sort(kd[i].begin(),kd[i].end());
		kd[i].erase(unique(kd[i].begin(),kd[i].end()),kd[i].end());
	}
	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