結果

問題 No.416 旅行会社
ユーザー vjudge1
提出日時 2024-12-23 20:31:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 966 ms / 4,000 ms
コード長 1,655 bytes
コンパイル時間 3,910 ms
コンパイル使用メモリ 260,824 KB
実行使用メモリ 37,008 KB
最終ジャッジ日時 2024-12-23 20:32:07
合計ジャッジ時間 13,484 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
template<typename T>istream&operator>>(istream&I,vector<T>&v){for(auto&i:v)I>>i;return I;}
template<typename T>ostream&operator<<(ostream&O,vector<T>&v){for(auto&i:v)O<<i<<' ';return O;}
namespace AC{
struct Dsu{
    vector<int>f,r;int si;
    Dsu(int n=0):si(n),f(n),r(n,1){iota(f.begin(),f.end(),0);}
    int&father(int x){return f[x];}
    int size(int x=-1){return x==-1?si:r[find(x)];}
    void clear(){for(int i=0;i<si;i++)f[i]=i,r[i]=1;}
    int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
    void merge(int x,int y){x=find(x),y=find(y),x!=y?r[x]>r[y]?(f[y]=x,r[x]+=r[y]):(f[x]=y,r[y]+=r[x]):0;}
    bool check(int x,int y){return find(x)==find(y);}
};
vector<int>g[100010];
int ans[100010],mark,vis[100010];
void dfs(int u){
    if(vis[u])return;
    vis[u]=1;
    ans[u]=mark;
    for(auto v:g[u])if(!vis[v])dfs(v);
}
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    Dsu dsu(n+1);
    set<pair<int,int>>mp;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        mp.insert({u,v});
        mp.insert({v,u});
    }
    vector<pair<int,int>>querys;
    for(int i=1;i<=q;i++){
        int u,v;
        cin>>u>>v;
        querys.push_back({u,v});
        mp.erase({u,v});
        mp.erase({v,u});
    }
    for(auto [u,v]:mp)g[u].push_back(v),g[v].push_back(u),dsu.merge(u,v);
    mark=-1,dfs(1);
    for(int i=q-1;i>=0;i--){
        auto[u,v]=querys[i];
        if(dsu.check(u,v))continue;
        if(dsu.check(u,1))mark=i+1,dfs(v);
        if(dsu.check(v,1))mark=i+1,dfs(u);
        dsu.merge(u,v);
        g[u].push_back(v),g[v].push_back(u);
    }
    for(int i=2;i<=n;i++)cout<<ans[i]<<'\n';
}
}
signed main(){
    int t=1;
    //cin>>t;
    while(t--)AC::solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0