結果

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

ソースコード

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=2e5+7;
struct edge{int nxt,to;}edge[N];
int hd[N],tot;
inline void addedge(int u,int v)
{
    edge[++tot].to=v;
    edge[tot].nxt=hd[u];
    hd[u]=tot;
}
int tim,dfn[N],low[N],bel[N],cnt;
vector<int>kd[N],ld[N],mp[N];
bool vis[N];
priority_queue<int,vector<int>,less<int>>val[N];
inline void Tarjan(int x,int fa)
{
    dfn[x]=low[x]=++tim;
    kd[x].push_back(x);
    for(int i=hd[x];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==fa)continue;
        if(!low[v])
        {
            Tarjan(v,x);
            for(auto s:kd[v])kd[x].emplace_back(s);
        }
        low[x]=min(low[x],low[v]);
    }
    return;
}
inline bool found(int x,int pos)
{
    bool fg=0;
    for(auto g:mp[x])
    {
        if(g==pos)return true;
        fg|=found(g,pos);
    }
    return fg;
}
bool outl=0;
inline void dfs(int x,int pos,int&v,int&p)
{
    for(auto g:kd[x])
    {
        if(g==pos)
        {
            int k;
            if(val[g].empty())k=-1;
            else k=val[g].top();
            if(k>v)v=k,p=g;
            outl=1;
            return;
        }
        if(!found(g,pos))continue;
        int k;
        if(val[g].empty())k=-1;
        else k=val[g].top();
        if(k>v)v=k,p=g;
        dfs(g,pos,v,p);
        if(outl)return;
    }
} 
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();
        addedge(u,v);
        addedge(v,u);
        ld[u].emplace_back(v);
        ld[v].emplace_back(u);
    } 
    Tarjan(1,0);
    for(int i=1;i<=n;++i)
        if(dfn[i]==low[i])
        {
            ++cnt;
            for(auto s:kd[i])bel[s]=cnt;
        }
    for(int i=1;i<=n;++i)kd[i].clear();
    for(int i=1;i<=n;++i)for(auto s:ld[i])if(s^bel[i])kd[bel[i]].emplace_back(bel[s]);
    for(int i=1;i<=cnt;++i)
    {
        sort(kd[i].begin(),kd[i].end());
        kd[i].erase(unique(kd[i].begin(),kd[i].end()),kd[i].end());
    }
    while(q--)
    {
        int op=read();
        if(op==1)
        {
            int u=read(),w=read();
            val[bel[u]].push(w);
        }
        if(op==2)
        {
            int s=read(),t=read();
            if(bel[s]==bel[t])
            {
                if(val[bel[s]].empty()){puts("-1");continue;}
                int v=val[bel[s]].top();
                val[bel[s]].pop();
                write(v),puts("");
                continue;
            }
            else
            {
                int v,x;
                if(val[bel[s]].empty())v=-1;
                else v=val[bel[s]].top();
                x=bel[s];
                outl=0;
                dfs(bel[s],bel[t],v,x);
                write(v),puts("");
                if(!val[x].empty())val[x].pop();
                continue;
            }
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0