結果

問題 No.416 旅行会社
ユーザー sntea
提出日時 2016-08-27 05:08:56
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 370 ms / 4,000 ms
コード長 5,339 bytes
コンパイル時間 2,167 ms
コンパイル使用メモリ 190,864 KB
実行使用メモリ 19,712 KB
最終ジャッジ日時 2024-12-14 20:01:07
合計ジャッジ時間 6,476 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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

#ifdef LOCAL111
#else
    #define NDEBUG
#endif
#include <bits/stdc++.h>
const int INF = 1e8;
using namespace std;
#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RBP(i,a) for(auto& i : a)
#ifdef LOCAL111
    #define DEBUG(x) cout<<#x<<": "<<(x)<<endl
    template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
    #define DEBUG(x) true
    template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
#define rangej(a,b,c) ((a) <= (c) and (c) < (b))
#define rrangej(b,c) rangej(0,b,c)
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;
typedef pair<LL,LL> LP;
void ios_init(){
    //cout.setf(ios::fixed);
    //cout.precision(12);
#ifdef LOCAL111
    return;
#endif
    ios::sync_with_stdio(false); cin.tie(0);    
}
//library
class uftree {
//private:
public:
    int *par;
    int *rank;
    int *num;
//public:
    uftree(int n)
    {
        par = new int[n];
        rank = new int[n];
        num = new int[n];
        for(int i = 0; i < n; i++){
            par[i] = i;
            rank[i] = 0;
            num[i] = 1;
        }
    }
    ~uftree()
    {
        delete[] par;
        delete[] rank;
        delete[] num;
    }
    int find(int x)
    {
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x] < rank[y]){
            par[x] = y;
            num[y] += num[x];
        }else{
            par[y] = x;
            num[x] += num[y];
            if(rank[x] == rank[y])  rank[x]++;
        }
    }
    int count(int x)
    {
        return num[find(x)];
    }
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
};
//library
//library
typedef int cost_t;
class Edge {
public:
    int to;
    cost_t cost;
    
    Edge(){
    }
    Edge(int x,cost_t y){
        to = x;
        cost = y;
    }
    bool operator< (const Edge& x) const {
        return cost < x.cost;
    }
    bool operator> (const Edge& x) const {
        return cost > x.cost;
    }
};
class Graph {
private:
    //const long long int INF = (long long)1e18;
    vector<vector<Edge> > v; 
    int n;
public:
    Graph(int x){
        n = x;
        v = vector<vector<Edge> >(x);
    }
    vector<Edge>& operator[](int x){
        return v[x];
    }
    const vector<Edge>& operator[](int x) const {
        return v[x];
    }
    int size() const {
        return n;
    }
    void add_edge(int from, Edge e){
        v[from].push_back(e);
    }
    void add_edge(int from, int to, cost_t cost){
        add_edge(from,Edge(to,cost));
    }
};
vector<cost_t> dijkstra(int from, const Graph& v) {
    vector<cost_t> dist(v.size(),INF);
    priority_queue<Edge,vector<Edge>,greater<Edge>> que;
    que.push(Edge(from,0));
    while(!que.empty()){
        Edge e = que.top();
        que.pop();
        if(dist[e.to] == INF){
            dist[e.to] = e.cost;
            for(auto to : v[e.to]){
                if(dist[to.to] == INF)
                    que.push(Edge(to.to, e.cost+to.cost));
            }
        }
    }
    return dist;
}
vector<cost_t> bellmanford(int from, const Graph& g){
    vector<cost_t> res(g.size(),INF);
    res[from] = 0;
    bool conf = true;
    int cnt = 0;
    while(conf){
        conf = false;
        for(int i = 0; i < g.size(); i++){
            if(res[i] != INF)
            for(const auto& e : g[i]){
                if(res[e.to] > res[i]+e.cost){
                    conf = true;
                    res[e.to] = res[i]+e.cost;
                }
            }
        }
        if(cnt > g.size()+5) return vector<cost_t>();
        cnt++;
    }
    return res;
}
Graph prim(const Graph g){
    using T = tuple<cost_t, int, int>;
    priority_queue<T, vector<T>, greater<T>> qu;
    int n = g.size();
    assert(n != 0);
    vector<bool> added(n,false);
    qu.emplace(0,0,0);
    Graph res(n);
    while(!qu.empty()){
        int from, to;
        cost_t cost;
        tie(cost, from, to) = qu.top();
        qu.pop();
        if(!added[to]){
            added[to] = true;
            res.add_edge(from, to, cost);
            res.add_edge(to, from, cost);
            for(const auto &e : g[to]){
                if(!added[e.to]){
                    qu.emplace(e.cost, to, e.to);
                }
            }
        }
    }
    return res;
}
//liblary
void dfs(const Graph &g, vector<int> &ans, int p,int num){
    if(ans[p] != -1) return ;
    ans[p] = num;
    DEBUG(num); DEBUG(p);
    RBP(e,g[p]){
        if(ans[p] != -1) dfs(g,ans,e.to,num);
    }
    return;
}
int main()
{
    ios_init();
    int n,m,q;
    cin >> n >> m >> q;
    uftree uf(n);
    set<P> edges;
    Graph g(n);
    REP(i,m){
        int a,b;
        cin >> a >> b;
        a--; b--;
        edges.emplace(a,b);
    }
    vector<P> qu(q);
    REP(i,q){
        int c,d;
        cin >> c >> d;
        c--; d--;
        qu[i] = P(c,d);
        edges.erase(P(c,d));
    }
    RBP(e,edges){
        uf.unite(e.F,e.S);
        g.add_edge(e.F,e.S,-1);
        g.add_edge(e.S,e.F,-1);
    }
    vector<int> ans(n,-1);
    RREP(i,q){
        DEBUG(i);
        bool f1 = uf.same(qu[i].F,0), f2 = uf.same(qu[i].S,0);
        if(f1^f2){
            if(f1){
                dfs(g,ans,qu[i].S,i+1);
            }else if(f2){
                dfs(g,ans,qu[i].F,i+1);
            }
        }
        g.add_edge(qu[i].F,qu[i].S,-1);
        g.add_edge(qu[i].S,qu[i].F,-1);
        uf.unite(qu[i].F, qu[i].S);
    }
    FOR(i,1,n){
        if(!uf.same(0,i)){
            ans[i] = 0;
        }
    }
    FOR(i,1,n){
        cout << ans[i] << endl;
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0