結果

問題 No.529 帰省ラッシュ
コンテスト
ユーザー CZS_AK_IOI2025
提出日時 2025-03-30 21:31:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,748 bytes
コンパイル時間 3,116 ms
コンパイル使用メモリ 217,204 KB
実行使用メモリ 28,904 KB
最終ジャッジ日時 2025-03-30 21:31:46
合計ジャッジ時間 15,334 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1 -- * 1
other -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
namespace IO{
	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*10+ch-'0',ch=getchar();
		return x*f;
	}
	inline void write(int x){
		if(x<0){
			putchar('-');
			x=-x;
		}
		if(x>=10)write(x/10);
		putchar(x%10+'0');
		return;
	}
}
using namespace IO;
int n,m,Q,dfcnt,low[maxn],dfn[maxn],belong[maxn],cnt,stk[maxn],top,siz[maxn];
map<pair<int,int>,bool>insigne;
vector<int>grath[maxn];
struct EDGE{int v,nxt;bool bridge;}edge[400040];
priority_queue<int>Tree[maxn*4];
int son[maxn],DFN[maxn],DFCNT,dep[maxn],Top[maxn],fa[maxn],MX,awmc,head[maxn],recnt=1;bool vis[maxn];
inline void addedge(int u,int v){
	edge[++recnt]={v,head[u],false};
	head[u]=recnt;
}
void Tarjan(int rt,int fa){
	dfn[rt]=low[rt]=++dfcnt;
	stk[++top]=rt;
	for(int j=head[rt];j;j=edge[j].nxt){
		int i=edge[j].v;
		if(i==fa)continue;
		if(!dfn[i]){
			Tarjan(i,rt);
			low[rt]=min(low[rt],low[i]);
			if(low[i]>dfn[rt])
				edge[j].bridge=edge[j^1].bridge=1;
		}
		else low[rt]=min(low[rt],dfn[i]);
	}
	return;
}
void dfs(int rt,int Fa){
	vis[rt]=1;siz[cnt]=1;belong[rt]=cnt;
	for(int i=head[rt];i;i=edge[i].nxt){
		if(edge[i].bridge)continue;
		int v=edge[i].v;
		if(v==Fa||vis[v])continue;
		dfs(v,rt);
	}
	return;
}
inline void dfs1(int rt,int Fa){
	siz[rt]=1;
	for(auto v:grath[rt]){
		if(v==Fa)continue;
		dep[v]=dep[rt]+1;
		fa[v]=rt;
		dfs1(v,rt);
		if(siz[v]>siz[son[rt]])son[rt]=v;
		siz[rt]+=siz[v];
	}
	return;
}
inline void dfs2(int rt,int tp,int Fa){
	DFN[rt]=++DFCNT;Top[rt]=tp;
	if(!son[rt])return;
	dfs2(son[rt],tp,rt);
	for(auto v:grath[rt]){
		if(v==Fa)continue;
		if(v==son[rt])continue;
		dfs2(v,v,rt);
	}
	return;
}
inline void build(int id,int l,int r){
	Tree[id].push(-1);
	int mid=(l+r)>>1;
	if(l==r)return;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	return;
}
inline void query(int id,int l,int r,int tol,int tor){
	if(l>tor||r<tol)return;
	if(l==r){
		if(Tree[id].top()>MX){
			MX=Tree[id].top();
			awmc=l;
		}
		return;
	}
	int mid=(l+r)>>1;
	if(!(mid<tol))query(id<<1,l,mid,tol,tor);
	if(!(mid+1>tor))query(id<<1|1,mid+1,r,tol,tor);
	return;
}
inline void AWMC(int id,int l,int r,int dlx){
	Tree[id].pop();
	if(l==r)return;int mid=(l+r)>>1;
	if(dlx<=mid)AWMC(id<<1,l,mid,dlx);
	else AWMC(id<<1|1,mid+1,r,dlx);
}
inline void update(int id,int l,int r,int place,int val){
	Tree[id].push(val);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(place<=mid)update(id<<1,l,mid,place,val);
	else update(id<<1|1,mid+1,r,place,val);
	return;
}
inline int QUERY(int u,int v){
	MX=-1;awmc=0;
	while(u!=v){
		if(dep[Top[v]]>dep[Top[u]])swap(u,v);
		query(1,1,n,DFN[Top[u]],DFN[u]);
		u=fa[Top[u]];
	}
	query(1,1,n,DFN[u],DFN[u]);
	if(awmc)AWMC(1,1,n,awmc);
	return MX;
}
signed main(){
	n=read();m=read();Q=read();siz[0]=-1;
	for(int i=1;i<=m;++i){
		int u=read(),v=read();
		addedge(u,v);addedge(v,u);
	}
	for(int i=1;i<=n;++i)if(!dfn[i])Tarjan(i,0);
	for(int i=1;i<=n;++i)if(!vis[i])++cnt,dfs(i,0);
	for(int i=1;i<=n;++i){
		for(int czs=head[i];czs;czs=edge[czs].nxt){
			int j=edge[czs].v;
			if(belong[i]!=belong[j]){
				int u=belong[i],v=belong[j];
				if(insigne[make_pair(u,v)])continue;
				if(insigne[make_pair(v,u)])continue;
				insigne[make_pair(v,u)]=insigne[make_pair(u,v)]=1;
				grath[u].push_back(v);
				grath[v].push_back(u);
			}
		}
	}
	dfs1(1,0);dfs2(1,1,0);build(1,1,n);
	for(int i=1;i<=Q;++i){
		int op=read();
		if(op==1){
			int u=read(),w=read();
			u=belong[u];
			update(1,1,n,DFN[u],w);
		}
		else{
			int u=read(),v=read();
			u=belong[u];v=belong[v];
			MX=-1;awmc=0;
			int AAANS=QUERY(u,v);
			write(AAANS);putchar('\n');
		}
	}
	return 0;
}
0