結果

問題 No.529 帰省ラッシュ
ユーザー 小夫
提出日時 2025-03-30 22:39:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 529 ms / 4,500 ms
コード長 3,536 bytes
コンパイル時間 2,757 ms
コンパイル使用メモリ 214,584 KB
実行使用メモリ 73,904 KB
最終ジャッジ日時 2025-03-30 22:40:04
合計ジャッジ時間 9,396 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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;
map<int,int>pos;
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;
}
struct trnode{int fa,dep,son,size,top,dfn;}tr[N];
struct sgnode{int maxn;}sg[N<<2];
inline void dfs1(int x,int fa,int d)
{
	tr[x].fa=fa,tr[x].dep=d,tr[x].size=1;
	int mx=-1;
    for(auto v:kd[x])
    {
        if(v==fa)continue;
        dfs1(v,x,d+1);
        tr[x].size+=tr[v].size;
        if(tr[v].size>mx)tr[x].son=v,mx=tr[v].size;
    }
}
inline void dfs2(int x,int top)
{
    tr[x].top=top,tr[x].dfn=++tim;
    if(tr[x].son)dfs2(tr[x].son,top);
    for(auto v:kd[x])
    {
        if(v==tr[x].fa||v==tr[x].son)continue;
        dfs2(v,v);
    }
    return;
}
#define lson (rt<<1)
#define rson (rt<<1|1)
inline void pushup(int rt){sg[rt].maxn=max(sg[lson].maxn,sg[rson].maxn);return;}
inline void build(int rt,int l,int r)
{
    if(l==r){sg[rt].maxn=-1;return;}
    int mid=l+r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(rt);
    return;
}
inline void modify(int rt,int l,int r,int pos,int val)
{
    if(pos<=l&&pos>=r)
    {
        sg[rt].maxn=val;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid)modify(lson,l,mid,pos,val);
    if(pos>mid)modify(rson,mid+1,r,pos,val);
    pushup(rt);
    return;
}
inline int querymax(int rt,int l,int r,int posl,int posr)
{
    if(posl<=l&&posr>=r)return sg[rt].maxn;
    int mid=l+r>>1,res=-1;
    if(posl<=mid)res=max(res,querymax(lson,l,mid,posl,posr));
    if(posr>mid)res=max(res,querymax(rson,mid+1,r,posl,posr));
    return res;
}
#undef lson
#undef rson
inline void modifydot(int x,int v)
{
	pos[v]=x,val[x].emplace(v);
	modify(1,1,cnt,tr[x].dfn,val[x].top());
	return;
}
inline int querychainmax(int x,int y)
{
    int res=-1;
	while(tr[x].top^tr[y].top)
	{
		if(tr[tr[x].top].dep<tr[tr[y].top].dep)swap(x,y);
		res=max(res,querymax(1,1,cnt,tr[tr[x].top].dfn,tr[x].dfn));
		x=tr[tr[x].top].fa;
	}
	if(tr[x].dep>tr[y].dep)swap(x,y);
	res=max(res,querymax(1,1,cnt,tr[x].dfn,tr[y].dfn));
	if(~res)
	{
		int p=pos[res]; 
		val[p].pop();
		modify(1,1,cnt,tr[p].dfn,val[p].empty()?-1:val[p].top());
	} 
	return res;
}
int main()
{
	//freopen("visit.in","r",stdin);
	//freopen("visit.out","w",stdout);
	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]);
	}
	tim=0;
	dfs1(1,1,0);
	dfs2(1,1);
	build(1,1,cnt);
	while(q--)
	{
		int op=read();
		if(op==1)
		{
			int u=bel[read()],w=read();
			modifydot(u,w);
		}
		if(op==2)
		{
			int s=bel[read()],t=bel[read()];
			write(querychainmax(s,t)),puts("");
		}
	}
    return 0;
}
0