結果

問題 No.529 帰省ラッシュ
ユーザー 小夫
提出日時 2025-03-30 22:39:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,532 bytes
コンパイル時間 2,984 ms
コンパイル使用メモリ 215,548 KB
実行使用メモリ 43,232 KB
最終ジャッジ日時 2025-03-30 22:40:00
合計ジャッジ時間 14,909 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1 -- * 1
other -- * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:147:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  147 |         freopen("visit.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:148:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  148 |         freopen("visit.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0