結果

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

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define maxn 600005
#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;
bool instk[maxn];int stk[maxn],top,sscval[maxn],siz[maxn];
vector<int>grath[maxn];
int head[maxn],recnt=1;bool vis[maxn];
struct EDGE{int v,nxt;bool bridge;}edge[4000040];
inline void addedge(int u,int v){
    edge[++recnt]={v,head[u],0};
    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],low[i]);
    }
    return;
}
void dfs(int rt,int Fa){
    vis[rt]=1;siz[cnt]++;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;
}
map<pair<int,int>,bool>mp;
priority_queue<int>Tree[maxn*4];
int son[maxn],DFN[maxn],DFCNT,dep[maxn],Top[maxn],fa[maxn];
inline void dfs1(int rt,int Fa){
    for(auto v:grath[rt]){
        if(v==Fa)continue;
        dep[v]=dep[rt]+1;
        dfs1(v,rt);
        if(siz[v]>siz[son[rt]])son[rt]=v;
        siz[rt]+=siz[v];
    }
    return;
}
inline void dfs2(int rt,int tp){
    DFN[rt]=++DFCNT;Top[rt]=tp;fa[son[rt]]=rt;
    if(son[rt])dfs2(son[rt],tp);
    for(auto v:grath[rt]){
        if(dep[v]<=dep[rt])continue;
        if(v==son[rt])continue;
        fa[v]=rt;
        dfs2(v,v);
    }
    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;
}
int MX,awmc;
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);
}
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){
    int U=u,V=v;MX=-1;awmc=0;
    query(1,1,n,DFN[u],DFN[u]);
    query(1,1,n,DFN[v],DFN[v]);
    while(u!=v){
        if(DFN[Top[v]]>DFN[Top[u]])swap(u,v);
        // cerr<<u<<" "<<v<<" "<<MX<<"\n";
        if(Top[u]==Top[v]){
            if(DFN[v]>DFN[u])swap(u,v);
            query(1,1,n,DFN[v],DFN[u]);
            break;
        }
        query(1,1,n,DFN[Top[u]],DFN[u]);
        u=fa[Top[u]];
    }
    if(awmc!=0)AWMC(1,1,n,awmc);
    return MX;
}
signed main(){
    // freopen("visit.in","r",stdin);
    // freopen("visit.out","w",stdout);
    n=read();m=read();q=read();
    while(m--){
        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(!mp.count(make_pair(min(u,v),max(u,v)))){
                    mp[make_pair(min(u,v),max(u,v))]=1;
                    grath[u].push_back(v);
                    grath[v].push_back(u);
                }
            }
        }
    }
    dfs1(1,0);dfs2(1,1);build(1,1,n);
    // for(int i=1;i<=n;++i){
    //     cerr<<"hou :"<<i<<" :::::"<<belong[i]<<" hou\n";
    // }
    while(q--){
        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