#664089 (C++14) No.1477 Lamps on Graph

提出ソース

結果

問題	No.1477 Lamps on Graph
ユーザー	altair_kyopro
提出日時	2021-06-05 20:39:43
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	175 ms / 2,000 ms
コード長	10,410 bytes
コンパイル時間	2,336 ms
コンパイル使用メモリ	190,840 KB
実行使用メモリ	11,272 KB
最終ジャッジ日時	2024-05-01 14:38:35
合計ジャッジ時間	8,844 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	65 ms 7,424 KB
testcase_13	AC	69 ms 6,940 KB
testcase_14	AC	77 ms 8,064 KB
testcase_15	AC	29 ms 6,940 KB
testcase_16	AC	22 ms 6,940 KB
testcase_17	AC	26 ms 6,940 KB
testcase_18	AC	114 ms 8,056 KB
testcase_19	AC	66 ms 7,040 KB
testcase_20	AC	23 ms 6,940 KB
testcase_21	AC	101 ms 7,140 KB
testcase_22	AC	13 ms 6,940 KB
testcase_23	AC	39 ms 6,944 KB
testcase_24	AC	100 ms 8,576 KB
testcase_25	AC	30 ms 6,940 KB
testcase_26	AC	99 ms 8,552 KB
testcase_27	AC	34 ms 6,940 KB
testcase_28	AC	43 ms 6,944 KB
testcase_29	AC	47 ms 6,940 KB
testcase_30	AC	68 ms 6,940 KB
testcase_31	AC	38 ms 6,940 KB
testcase_32	AC	175 ms 11,272 KB
testcase_33	AC	133 ms 10,528 KB
testcase_34	AC	168 ms 8,280 KB
testcase_35	AC	130 ms 10,304 KB
testcase_36	AC	126 ms 10,304 KB
testcase_37	AC	88 ms 10,240 KB
testcase_38	AC	102 ms 10,176 KB
testcase_39	AC	127 ms 10,308 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifdef __LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using PIL = pair<int,ll>;
using PLI = pair<ll,int>;
using PLL = pair<ll,ll>;

template<class T> bool chmin(T &a, T b) {if(a>b){a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b){a=b;return 1;}return 0;}
template<class T> void show_vec(T v) {for (int i=0;i<v.size();i++) cout<<v[i]<<endl;}
template<class T> void show_pair(T p) {cout<<p.first<<" "<<p.second<<endl;}
template<class T> bool judge_digit(T bit,T i) {return (((bit&(1LL<<i))!=0)?1:0);}
#define REP(i,n) for(int i=0;i<int(n);i++)
#define ROUNDUP(a,b) (((a)+(b)-1)/(b))
#define YESNO(T) cout<<(T?"YES":"NO")<<endl
#define yesno(T) cout<<(T?"yes":"no")<<endl
#define YesNo(T) cout<<(T?"Yes":"No")<<endl

const int INFint = 1 << 29;
const ll INF = 1LL << 60;
const ll MOD = 1000000007LL;
const double pi = 3.14159265358979;
const vector<int> h_idx4 = {-1, 0,0,1};
const vector<int> w_idx4 = { 0,-1,1,0};
const vector<int> h_idx8 = {-1,-1,-1, 0,0, 1,1,1};
const vector<int> w_idx8 = {-1, 0, 1,-1,1,-1,0,1};



struct edge {
    int to; ll cost;
    edge() = default;
    edge(int _to,ll _cost) : to(_to), cost(_cost) {}

    // 不等号を定義
    bool operator<(const edge &other) const {
        return cost < other.cost;
    }
    bool operator>(const edge &other) const {
        return cost > other.cost;
    }
};
struct Edge {
    int from; int to; ll cost;
    Edge() = default;
    Edge(int _from, int _to,ll _cost) : from(_from), to(_to), cost(_cost) {}

    // 不等号を定義
    bool operator<(const Edge &other) const {
        return cost < other.cost;
    }
    bool operator>(const Edge &other) const {
        return cost > other.cost;
    }
};

struct DSU {
  public:
    DSU() : n(0) {}
    DSU(int _n) : n(_n), parent_or_size(_n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < n);
        assert(0 <= b && b < n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < n);
        assert(0 <= b && b < n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < n);
        return -parent_or_size[leader(a)];
    }

    vector<vector<int>> groups() {
        vector<int> leader_buf(n), group_size(n);
        for (int i = 0; i < n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        vector<vector<int>> result(n);
        for (int i = 0; i < n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            remove_if(result.begin(), result.end(),
                           [&](const vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int n;
    // root node: -1 * component size
    // otherwise: parent
    vector<int> parent_or_size;
};

struct Graph {
  private:
    vector<vector<edge>> G;
    int n,m;

  public:
    vector<int> indegree;
    inline const std::vector<edge> &operator[](int k) const { return G[k]; }
	inline std::vector<edge> &operator[](int k) { return G[k]; }
    int size() const { return G.size(); }
	void resize(const int n) { G.resize(n); }

    Graph() = default;
    Graph(int _n) : n(_n), G(_n), indegree(_n) {}
    Graph(int _n, int _m, bool weight, bool directed, int index) : n(_n), m(_m), G(_n), indegree(_n,0) { input(weight,directed,index); }

    void input(bool weight, bool directed, int index){
        int _from, _to; ll _cost = 1;
        for (int i = 0; i < m; i++){
            cin >> _from >> _to;
            _from -= index; _to -= index;
            if (weight) cin >> _cost;

            G[_from].push_back(edge(_to,_cost));
            if (!directed) G[_to].push_back(edge(_from,_cost));

            indegree[_to]++;

        }
    }

    // 重みなしグラフの始点からの最短距離を求める
    // 到達不可能点 : -1
    // O(N + M)
    vector<int> BFS(int start){
        vector<int> dist(n,-1);
        dist[start] = 0;

        queue<int> que;
        que.push(start);

        while (!que.empty()){
            int now = que.front();
            que.pop();

            for (auto &e : G[now]){
                if (dist[e.to] != -1) continue;

                dist[e.to] = dist[now] + 1;
                que.push(e.to);
            }
        }

        return dist;
    }

    // 辺長が 0or1 のグラフをに対し単一始点最短距離を求める (01BFS)
    // 到達不可能点 : INF
    // O(N + M)
    vector<ll> Zero_One_BFS(int start){
        vector<ll> dist(n,INF);
        dist[start] = 0LL;

        deque<int> que;
        que.push_back(start);

        while (!que.empty()){
            auto now = que.front();
            que.pop_front();

            for (auto &e : G[now]){
                ll next_d = dist[now] + e.cost;
                if (chmin(dist[e.to], next_d)){
                    if (e.cost == 0) que.push_front(e.to);
                    else que.push_back(e.to);
                }
            }
        }

        return dist;
    }

    // 重み付きグラフの単一始点最短距離を求める
    // 負辺を持たない
    // 到達不可能点 : INF
    // O((N + M)logN)
    vector<ll> Dijkstra(int start){
        vector<ll> dist(n,INF);
        dist[start] = 0LL;

        priority_queue<edge, vector<edge>, greater<edge>> pq;
        pq.push(edge(start,0LL));

        while (!pq.empty()){
            auto p = pq.top();
            pq.pop();

            int now = p.to;
            if (dist[now] < p.cost) continue;

            for (auto &e : G[now]){
                ll next_d = dist[now] + e.cost;
                if (chmin(dist[e.to],next_d)){
                    pq.push(edge(e.to, dist[e.to]));
                }
            }
        }

        return dist;
    }

    // 負辺をもつ重み付きグラフの単一始点最短距離を求める
    // 到達不可能点 : INF
    // 負閉路 : -INF
    // O(NM)
    vector<ll> Bellman_Ford(int start){
		vector<ll> dist(n, INF);
		dist[start] = 0LL;
		for (int loop = 0; loop < n - 1; loop++){
			for (int v = 0; v < n; v++){
				if (dist[v] == INF) continue;

				for (auto &e : G[v]){
                    ll next_d = dist[v] + e.cost;
                    chmin(dist[e.to],next_d);
				}
			}
		}

		queue<int> que;
		vector<bool> chk(n,false);

		for (int v = 0; v < n; v++){
			if (dist[v] == INF) continue;

			for (auto &e : G[v]){
                ll next_d = dist[v] + e.cost;
				if (dist[e.to] > next_d && !chk[e.to]){
					que.push(e.to);
					chk[e.to] = true;
				}
			}
		}

		while (!que.empty()){
			int now = que.front();
			que.pop();

			for (auto &e : G[now]){
				if (!chk[e.to]){
					chk[e.to] = true;
					que.push(e.to);
				}
			}
		}

		for (int i = 0; i < n; i++) if (chk[i]) dist[i] = -INF;

		return dist;
	}

    // 重み付きグラフの全頂点対間最短距離を求める
    // 到達不可能点 : INF 
    // O(N^3)
    vector<vector<ll>> Warshall_Floyd(){
        vector<vector<ll>> dist(n, vector<ll>(n,INF));
        for (int i = 0; i < n; i++) dist[i][i] = 0LL;
        for (int i = 0; i < n; i++){
            for (auto &e : G[i]) chmin(dist[i][e.to], e.cost);
        }

        for (int k = 0; k < n; k++){
            for (int i = 0; i < n; i++){
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < n; j++){
                    if (dist[k][j] == INF) continue;
                    chmin(dist[i][j],dist[i][k] + dist[k][j]);
                }
            }
        }

        return dist;
    }

    // 最小全域木の辺の重みの総和
    // Gが非連結 : -1
    // O(MlogM)
    ll Kruskal(){
        vector<Edge> E;
        for (int i = 0; i < n; i++){
            for (auto &e : G[i]){
                E.push_back(Edge(i,e.to,e.cost));
            }
        }
        sort(E.begin(), E.end());

        DSU uf(n);
        ll res = 0;
        sort(E.begin(), E.end());
        for (auto &e : E){
            if (!uf.same(e.from,e.to)){
                uf.merge(e.from,e.to);
                res += e.cost;
            }
        }

        if (uf.size(0) != n) return -1;

        return res;
    }

	// DGAをトポロジカルソートする
	// O(V+E)
	vector<int> topological_sort(){
		vector<int> res;
		queue<int> que;

		for (int i = 0; i < n; i++){
			if (indegree[i] == 0){
				que.push(i);
			}
		}

		while (!que.empty()){
			int x = que.front();
			que.pop();

			for (auto e : G[x]){
				indegree[e.to]--;
				if (indegree[e.to] == 0) que.push(e.to);
			}

			res.push_back(x);
		}

		return res;
	}


};

int n,m;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);

	cin >> n >> m;
    vector<ll> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    Graph G(n);
    for (int i = 0; i < m; i++){
        int from,to;
        cin >> from >> to;
        from--; to--;

        if (a[from] < a[to]){
            G[from].push_back(edge(to,1LL));
            G.indegree[to]++;
        }
        if (a[to] < a[from]){
            G[to].push_back(edge(from,1LL));
            G.indegree[from]++;
        }
    }

    int k;
    cin >> k;
    vector<bool> lamps(n,false);
    for (int i = 0; i < k; i++){
        int b;
        cin >> b; b--;
        lamps[b] = true;
    }

    vector<int> topo = G.topological_sort();

    // for (int i = 0; i < n; i++){
    //     cout << topo[i] << " ";
    // }
    // cout << endl;

    vector<int> op;
    for (int i = 0; i < n; i++){
        int now = topo[i];
        if (lamps[now]){
            op.push_back(now);
            lamps[now] = false;
            for (auto e : G[now]){
                lamps[e.to] = !lamps[e.to];
            }
        }
    }

    cout << op.size() << endl;
    for (auto i : op){
        cout << i + 1 << endl;
    }

}

yukicoder

結果

テストケース

ソースコード