結果

問題 No.529 帰省ラッシュ
ユーザー CZS_AK_IOI2025
提出日時 2025-03-30 22:19:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 675 ms / 4,500 ms
コード長 4,128 bytes
コンパイル時間 3,178 ms
コンパイル使用メモリ 219,564 KB
実行使用メモリ 70,856 KB
最終ジャッジ日時 2025-03-30 22:19:10
合計ジャッジ時間 10,218 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 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],deep[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 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){
    ++recnt;
    edge[recnt].v=v;
    edge[recnt].nxt=head[u];
    edge[recnt].bridge=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;deep[rt]=deep[Fa]+1;
    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]=-1;
    int mid=(l+r)>>1;
    if(l==r){Tree[id].push(-1);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;
    }
    if(tree[id]<=MX)return;
    int mid=(l+r)>>1;
    if(tree[id<<1]>tree[id<<1|1])query(id<<1,l,mid,tol,tor),query(id<<1|1,mid+1,r,tol,tor);
    else query(id<<1|1,mid+1,r,tol,tor),query(id<<1,l,mid,tol,tor);
    return;
}
inline void AWMC(int id,int l,int r,int dlx){
    if(l==r){Tree[id].pop();tree[id]=Tree[id].top();return;}
    int mid=(l+r)>>1;
    if(dlx<=mid)AWMC(id<<1,l,mid,dlx);
    else AWMC(id<<1|1,mid+1,r,dlx);
    tree[id]=max(tree[id<<1],tree[id<<1|1]);
    return;
}
inline void update(int id,int l,int r,int place,int val){
    if(l==r){Tree[id].push(val);tree[id]=Tree[id].top();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);
    tree[id]=max(tree[id<<1],tree[id<<1|1]);
    return;
}
inline int QUERY(int u,int v){
    MX=-1;awmc=0;
    while(Top[u]!=Top[v]){
        if(deep[Top[v]]>deep[Top[u]])swap(u,v);
        query(1,1,n,DFN[Top[u]],DFN[u]);
        u=fa[Top[u]];
    }
    if(DFN[v]>DFN[u])swap(u,v);
    query(1,1,n,DFN[v],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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0