結果

問題 No.416 旅行会社
ユーザー vjudge1
提出日時 2024-12-22 23:20:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,849 bytes
コンパイル時間 2,025 ms
コンパイル使用メモリ 179,400 KB
実行使用メモリ 846,452 KB
最終ジャッジ日時 2024-12-22 23:21:32
合計ジャッジ時間 41,396 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 1 TLE * 5 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

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

#include<bits/stdc++.h>
//#define int long long
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<<3)+(x<<1)+ch-48;ch=getchar();}
   return x*f;
}
void write(int x)
{
   if(x<0)putchar('-'),x=-x;
   if(x<10)putchar(x+'0');
   else write(x/10),putchar(x%10+'0');
}
const int N=2e5;
const int mod=1e9+7;
int n,m,q;
int ans[N];
int f[N];
struct node{
    int u,v;
}mp[N],a[N];
vector<int>g[N];
set<int>s[N];
set<int>ss[N];
int root(int x){
    if(f[x]==x)return x;
    int k=root(f[x]);
    for(int i=0;i<g[x].size();i++)if(ss[k].count(g[x][i])==0)g[k].push_back(g[x][i]),ss[k].insert(g[x][i]);
    g[x].clear(); 
    return f[x]=k;
}
signed main(){
//  freopen("evacuate.in","r",stdin);
//  freopen("evacuate.out","w",stdout);
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++)f[i]=i,g[i].push_back(i),s[i].insert(i);
    for(int i=1;i<=m;i++)
        mp[i].u=read(),mp[i].v=read(),s[mp[i].u].insert(mp[i].v),s[mp[i].v].insert(mp[i].u);
    for(int i=1;i<=q;i++)a[i].u=read(),a[i].v=read(),s[a[i].u].erase(a[i].v),s[a[i].v].erase(a[i].u);
    for(int i=1;i<=n;i++){
        while(!s[i].empty()){
            int k=*s[i].begin();
            if(f[root(k)]!=root(i)){
            f[root(k)]=root(i);
            int CCC=root(k);
            g[i].push_back(k);
        
        }
            s[i].erase(k);
         }
     }
     int fa=root(1);
     for(int i=2;i<=n;i++)
     if(root(i)==fa)ans[i]=-1;
     for(int i=q;i>=1;i--){
        int x=root(a[i].u);
        int y=root(a[i].v);
        int ff=root(1); 
        f[root(x)]=root(y); 
        fa=root(1);
        if(root(a[i].u)==fa){
            int z=fa;
            if(!ans[z])
            ans[z]=i;
            for(int j=0;j<g[z].size();j++){
                if(ans[g[z][j]]==0)ans[g[z][j]]=i;
            }
            g[z].clear();
        }
        else{
            g[root(a[i].u)].push_back(root(a[i].v));
            g[root(a[i].v)].push_back(root(a[i].u));
        }
     }
     for(int i=2;i<=n;i++)cout<<ans[i]<<"\n";
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0