結果

問題 No.416 旅行会社
ユーザー btk
提出日時 2016-08-26 23:52:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 526 ms / 4,000 ms
コード長 2,595 bytes
コンパイル時間 2,467 ms
コンパイル使用メモリ 197,324 KB
実行使用メモリ 23,812 KB
最終ジャッジ日時 2024-12-14 19:57:02
合計ジャッジ時間 8,836 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

struct I{
    I(){
        ios::sync_with_stdio(false);cin.tie(0);
    }
}init;
namespace _DSU{
#define SZ 200000
    int par[SZ];
    int rank[SZ];
}
class UnionFind{
private:
    int *par,*rank;
    int find(int x){
	if (par[x] == x) return x;
	else {
            return par[x] = find(par[x]);
        }
    }
public:
    UnionFind(int n) :
        par(_DSU::par),
        rank(_DSU::rank){
	for(int i = 0; i < n; i++)
            par[i] = i,rank[i] = 0;
    }
    bool unite(int x, int y){
	x = find(x);y = find(y);
	if (x == y)return false;
	if (rank[x] < rank[y]) par[x] = y;
	else{
	    par[y] = x;
	    if (rank[x] == rank[y])rank[x]++;
	}
	return true;
    }
    bool same(int x, int y){
	return find(x) == find(y);
    }
    
};
int main(){
    int N,M,Q;cin>>N>>M>>Q;
    vector<int> a(M),b(M),c(Q),d(Q);
    for(int i=0;i<M;a[i]--,b[i]--,i++)cin>>a[i]>>b[i];
    for(int i=Q-1;i>=0;c[i]--,d[i]--,i--)cin>>c[i]>>d[i];
    using P=pair<int,int>;
    
    set<P> memo;    
    UnionFind uf(N);
    vector<bool> used(M,false);
    for(int i=0;i<Q;i++)
        memo.insert(minmax(c[i],d[i]));
    for(int i=0;i<M;i++)
        if(memo.count(minmax(a[i],b[i]))==0)
            used[i]=true;

    
    using node=tuple<int,int,vector<int>>;
    vector<int> s(N-1),connect(N,0);
    iota(s.begin(),s.end(),1);
    queue<node> que;
    que.push(node(-1,Q-1,s));
    while(que.size()){
        queue<node> nxt;
        UnionFind uf(N);
        
        for(int i=0;i<M;i++)if(used[i])uf.unite(a[i],b[i]);
        int id=0;
        while(que.size()){
            auto now=que.front();que.pop();
            int bg,ed;vector<int> v;
            tie(bg,ed,v)=now;

            if(ed-bg<=1)for(auto &u:v)connect[u]=Q-ed;
            else{
                int half=(bg+ed)/2;
                for(;id<=half;id++)uf.unite(c[id],d[id]);
                vector<int> L,R;
                for(auto &u:v)
                    if(uf.same(0,u))
                        L.push_back(u);
                    else
                        R.push_back(u);
                nxt.push(node(bg,half,L));
                nxt.push(node(half,ed,R));
            }
            for(;id<=ed;id++)uf.unite(c[id],d[id]);
        }
        swap(que,nxt);
    }

    UnionFind check(N);
    for(int i=0;i<M;i++)if(used[i])check.unite(a[i],b[i]);
    for(int i=1;i<N;i++)if(check.same(0,i))connect[i]=-1;
    for(int i=0;i<M;i++)check.unite(a[i],b[i]);
    for(int i=1;i<N;i++)if(!check.same(0,i))connect[i]=0;
    for(int i=1;i<N;i++)cout<<connect[i]<<endl;
    
    
    return 0;
}
0