B - 駐車場 arc056_b

Quiz

https://atcoder.jp/contests/arc056/tasks/arc056_b

Submit

https://atcoder.jp/contests/arc056/submissions/4410100

Note

  • 通れる部分が減っていく。i番目の車を入れたらiからのびる辺が消えてグラフが分断されていく
  • union findの逆でグループ分けを効率的にやる方法がある？→ない

気づくべきポイント

  • iに行くまでの辺でi未満の点を通らなければいけない場合は（もう埋まっているので）通れない
  • 逆にi以上の点のみを辿って行けるなら、（まだ埋まっていないので）行ける

editorialが簡潔に書かれすぎていて分からない場合

自分でグラフを書いて「ダイクストラもどき」をシミュレーションする

f:id:peroon:20190228151020j:plain

ステップ

  • 観察により、iの車のとき、i未満の点を通らねばならない時は行けない
    • 経由する点で決まる
  • 経由する点の最小値を、各点に行くためのコストとする
  • それを求めるために、ダイクストラの応用をする

Code

#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

template < typename T >
void vprint(T &V){
    for(auto v : V){
        cout << v << " ";
    }
    cout << endl;
}

const ll mod = 1e9 + 7;
const ll inf = 1e18;

const int N_MAX = 200010;
vector<vector<ll> > G;

struct Node{
    ll id;
    ll cost;
    Node(){}
    Node(ll i, ll c){
        id = i;
        cost = c;
    }

    bool operator<(const Node &another) const
    {
        return cost < another.cost;
    }

    string ToString(){
        stringstream ss;
        ss << "node " << id << " " << cost;
        return ss.str();
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N, M, S;
    cin >> N >> M >> S;

    ll cost[N+1];
    bool fixed[N+1];
    FOR(i, 0, N+1){
        cost[i] = 0;
        fixed[i] = false;
    }

    G.resize(N+1);

    // エッジ情報
    FOR(i, 0, M){
        ll u, v;
        cin >> u >> v;

        G[u].push_back(v);
        G[v].push_back(u);
    }

    // 始点
    cost[S] = S;
    
    priority_queue<Node> que;
    que.push(Node(S, S));

    while(!que.empty()){
        auto node = que.top();
        que.pop();

        if(fixed[node.id]){
            continue;
        }else{
            fixed[node.id] = true;
            cost[node.id] = node.cost;
        }

        auto list = G[node.id];
        for(ll to : list){
            ll cost = min(node.cost, to);
            que.push(Node(to, cost));
        }
    }

    FOR(i, 1, N+1){
        if(cost[i]==i){
            p(i);
        }
    }
    
    return 0;
}