Submission #18369924


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <atcoder/all>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

struct Edge {
    int u,v,c;
};
void solve() {
    int N,M; cin >> N >> M;
    auto kruskal = [&]()->vector<set<pair<int,int>>> {
        // 辺集合
        vector<Edge> edges(M);
        REP(i,M) {
            int v1,v2,c; cin >> v1 >> v2 >> c;
            v1--; v2--;
            edges[i] = Edge{v1,v2,c};
        }

        atcoder::dsu uf(N);
        // key < val とする。
        vector<set<pair<int,int>>> g(N,set<pair<int,int>>());
        for(const auto &edge: edges) {
            // 木構造になっていたら終わり
            if(uf.size(0) == N) break;
            if(uf.same(edge.u,edge.v)) continue;
            // swap したいのでコピー
            g[edge.u].emplace(edge.v,edge.c);
            g[edge.v].emplace(edge.u,edge.c);
        }
        return g;
    };
    auto tree = kruskal();
    // rootノードを決める
    int root = -1;
    REP(i,N) if(!tree[i].empty()) {
        root = i;
        break;
    }
    assert(root != -1);
    // 良い書き方を作成していく
    auto bfs = [&]() {
        vector<int> vals(N,-1);
        vals[root] = 1;
        // pos, parent val
        queue<int> q;
        q.push(root);
        while(!q.empty()) {
            auto pos = q.front(); q.pop();
            for(const auto &child: tree[pos]) {
                auto [next,next_label] = child;
                if(vals[next] != -1) continue;
                if(next_label != vals[pos])vals[next] = next_label;
                else vals[next] = (next_label%N)+1;
                q.push(next);
            }
        }

        for(const auto &it: vals) cout << it << endl;
    };

    bfs();
}

int main() {
    solve();
    return 0;
}

Submission Info

Submission Time
Task C - Keep Graph Connected
User reud
Language C++ (GCC 9.2.1)
Score 500
Code Size 2268 Byte
Status AC
Exec Time 266 ms
Memory 26880 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 1
AC × 86
Set Name Test Cases
Sample sample_01.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, hand_13.txt, hand_14.txt, hand_15.txt, hand_16.txt, hand_17.txt, hand_18.txt, hand_19.txt, hand_20.txt, hand_21.txt, hand_22.txt, hand_23.txt, hand_24.txt, hand_25.txt, hand_26.txt, hand_27.txt, hand_28.txt, hand_29.txt, hand_30.txt, hand_31.txt, hand_32.txt, hand_33.txt, hand_34.txt, hand_35.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt, random_40.txt, random_41.txt, random_42.txt, random_43.txt, random_44.txt, random_45.txt, random_46.txt, random_47.txt, random_48.txt, random_49.txt, random_50.txt, sample_01.txt
Case Name Status Exec Time Memory
hand_01.txt AC 8 ms 3524 KB
hand_02.txt AC 2 ms 3496 KB
hand_03.txt AC 3 ms 3532 KB
hand_04.txt AC 2 ms 3408 KB
hand_05.txt AC 5 ms 3416 KB
hand_06.txt AC 3 ms 3528 KB
hand_07.txt AC 2 ms 3416 KB
hand_08.txt AC 3 ms 3416 KB
hand_09.txt AC 1 ms 3524 KB
hand_10.txt AC 2 ms 3464 KB
hand_11.txt AC 122 ms 16500 KB
hand_12.txt AC 114 ms 15000 KB
hand_13.txt AC 113 ms 15772 KB
hand_14.txt AC 59 ms 9332 KB
hand_15.txt AC 59 ms 9752 KB
hand_16.txt AC 69 ms 10772 KB
hand_17.txt AC 38 ms 6620 KB
hand_18.txt AC 154 ms 18724 KB
hand_19.txt AC 62 ms 10036 KB
hand_20.txt AC 99 ms 13560 KB
hand_21.txt AC 59 ms 9264 KB
hand_22.txt AC 134 ms 16876 KB
hand_23.txt AC 80 ms 12768 KB
hand_24.txt AC 118 ms 16080 KB
hand_25.txt AC 118 ms 16560 KB
hand_26.txt AC 23 ms 5272 KB
hand_27.txt AC 25 ms 6028 KB
hand_28.txt AC 162 ms 18664 KB
hand_29.txt AC 92 ms 14388 KB
hand_30.txt AC 48 ms 7960 KB
hand_31.txt AC 140 ms 18756 KB
hand_32.txt AC 159 ms 18728 KB
hand_33.txt AC 142 ms 18780 KB
hand_34.txt AC 155 ms 18748 KB
hand_35.txt AC 142 ms 18780 KB
random_01.txt AC 5 ms 3540 KB
random_02.txt AC 2 ms 3496 KB
random_03.txt AC 2 ms 3536 KB
random_04.txt AC 3 ms 3408 KB
random_05.txt AC 3 ms 3584 KB
random_06.txt AC 3 ms 3536 KB
random_07.txt AC 1 ms 3624 KB
random_08.txt AC 3 ms 3412 KB
random_09.txt AC 3 ms 3416 KB
random_10.txt AC 2 ms 3524 KB
random_11.txt AC 2 ms 3524 KB
random_12.txt AC 3 ms 3496 KB
random_13.txt AC 2 ms 3588 KB
random_14.txt AC 4 ms 3448 KB
random_15.txt AC 2 ms 3600 KB
random_16.txt AC 2 ms 3524 KB
random_17.txt AC 2 ms 3532 KB
random_18.txt AC 2 ms 3416 KB
random_19.txt AC 2 ms 3524 KB
random_20.txt AC 3 ms 3528 KB
random_21.txt AC 11 ms 3628 KB
random_22.txt AC 4 ms 3432 KB
random_23.txt AC 14 ms 3772 KB
random_24.txt AC 11 ms 3552 KB
random_25.txt AC 5 ms 3552 KB
random_26.txt AC 12 ms 3592 KB
random_27.txt AC 5 ms 3560 KB
random_28.txt AC 9 ms 3576 KB
random_29.txt AC 9 ms 3568 KB
random_30.txt AC 10 ms 3720 KB
random_31.txt AC 51 ms 8700 KB
random_32.txt AC 19 ms 4708 KB
random_33.txt AC 22 ms 5640 KB
random_34.txt AC 80 ms 12976 KB
random_35.txt AC 52 ms 9072 KB
random_36.txt AC 42 ms 7412 KB
random_37.txt AC 47 ms 8220 KB
random_38.txt AC 100 ms 15468 KB
random_39.txt AC 70 ms 11380 KB
random_40.txt AC 98 ms 14820 KB
random_41.txt AC 115 ms 15280 KB
random_42.txt AC 128 ms 16824 KB
random_43.txt AC 143 ms 18132 KB
random_44.txt AC 266 ms 26880 KB
random_45.txt AC 192 ms 21040 KB
random_46.txt AC 63 ms 9520 KB
random_47.txt AC 241 ms 25580 KB
random_48.txt AC 254 ms 26268 KB
random_49.txt AC 149 ms 18608 KB
random_50.txt AC 88 ms 13484 KB
sample_01.txt AC 8 ms 3480 KB