Submission #486325


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(c) begin(c),end(c)

typedef vector<vector<int>> graph;
class maximal_indsets {
    const int n;
    const graph& G;
    vector<vector<int>> ret;
    vector<int> cur, exists, deg, block;
    void erase(int v) {
        if (exists[v]) {
            exists[v] = false;
            for (int nv : G[v]) --deg[nv];
        }
    }
    void restore(int v) {
        exists[v] = true;
        for (int nv : G[v]) ++deg[nv];
    }
    void select(int v) {
        cur.push_back(v);
        ++block[v], erase(v);
        for (int nv : G[v]) ++block[nv], erase(nv);
    }
    void unselect(int v) {
        cur.pop_back();
        --block[v], restore(v);
        for (int nv : G[v]) {
            if (--block[nv] == 0) restore(nv);
        }
    }
    void dfs() {
        int mn = n, v = -1;
        rep(u, n) if (exists[u]) {
            if (deg[u] < mn) mn = deg[u], v = u;
        }
        if (v == -1) {
            ret.push_back(cur);
        } else {
            select(v), dfs(), unselect(v);
            for (int nv : G[v]) {
                if (exists[nv]) select(nv), dfs(), unselect(nv);
            }
        }
    }
public:
    maximal_indsets(const graph& G) : n(G.size()), G(G), exists(n, true), deg(n), block(n) {
        rep(v, n) deg[v] = G[v].size();
        dfs();
    }
    const vector<vector<int>>& get() const { return ret; }
};

int n, m, k;
graph G;

void input()
{
    cin >> n >> m >> k;
    G.assign(n, vector<int>());
    rep(_, m) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

vector<int> solve()
{
    vector<int> ans;
    vector<int> done(n, 0);
    rep(i, n) if (not done[i]) {
        queue<int> que;
        que.push(i), done[i] = true;
        vector<int> sub;
        while (not que.empty()) {
            int v = que.front();
            que.pop();
            sub.push_back(v);
            for (int nv : G[v]) {
                if (not done[nv]) {
                    que.push(nv);
                    done[nv] = true;
                }
            }
        }
        const int vsub = sub.size();
        vector<int> zip(n, -1);
        rep(i, vsub) zip[sub[i]] = i;
        graph Gsub(vsub, vector<int>());
        rep(v, n) {
            if (zip[v] == -1) continue;
            for(int nv:G[v]) {
                if (zip[nv] == -1) continue;
                Gsub[zip[v]].push_back(zip[nv]);
            }
        }
        auto res = maximal_indsets(Gsub).get();
        int best = 0, id = -1;
        rep(i, res.size()) {
            const auto& inds = res[i];
            if (int(inds.size()) > best) {
                best = inds.size();
                id = i;
            }
        }
        if (id != -1) {
            for (int v : res[id]) {
                ans.push_back(sub[v]);
            }
            if (int(ans.size()) >= k) {
                ans.erase(begin(ans) + k, end(ans));
                return ans;
            }
        }
    }
    return vector<int>();
}

int main()
{
    input();
    auto ans = solve();
    for (int v : ans) {
        cout << v << endl;
    }
}

Submission Info

Submission Time
Task B - B 問題
User miki_im
Language C++11 (GCC 4.9.2)
Score 10
Code Size 3465 Byte
Status
Exec Time 29 ms
Memory 932 KB

Test Cases

Set Name Score / Max Score Test Cases
All 10 / 10 00_sample_1.txt, 00_sample_2.txt, 00_sample_3.txt, 20_random_1.txt, 20_random_10.txt, 20_random_11.txt, 20_random_12.txt, 20_random_13.txt, 20_random_14.txt, 20_random_15.txt, 20_random_16.txt, 20_random_17.txt, 20_random_18.txt, 20_random_19.txt, 20_random_2.txt, 20_random_20.txt, 20_random_21.txt, 20_random_22.txt, 20_random_23.txt, 20_random_24.txt, 20_random_25.txt, 20_random_26.txt, 20_random_27.txt, 20_random_28.txt, 20_random_29.txt, 20_random_3.txt, 20_random_30.txt, 20_random_4.txt, 20_random_5.txt, 20_random_6.txt, 20_random_7.txt, 20_random_8.txt, 20_random_9.txt
Case Name Status Exec Time Memory
00_sample_1.txt 26 ms 928 KB
00_sample_2.txt 26 ms 916 KB
00_sample_3.txt 25 ms 800 KB
20_random_1.txt 25 ms 924 KB
20_random_10.txt 24 ms 800 KB
20_random_11.txt 26 ms 732 KB
20_random_12.txt 25 ms 924 KB
20_random_13.txt 26 ms 928 KB
20_random_14.txt 24 ms 924 KB
20_random_15.txt 25 ms 920 KB
20_random_16.txt 24 ms 804 KB
20_random_17.txt 26 ms 916 KB
20_random_18.txt 26 ms 808 KB
20_random_19.txt 27 ms 804 KB
20_random_2.txt 26 ms 800 KB
20_random_20.txt 26 ms 928 KB
20_random_21.txt 27 ms 796 KB
20_random_22.txt 26 ms 920 KB
20_random_23.txt 26 ms 924 KB
20_random_24.txt 24 ms 800 KB
20_random_25.txt 25 ms 804 KB
20_random_26.txt 26 ms 924 KB
20_random_27.txt 26 ms 804 KB
20_random_28.txt 25 ms 928 KB
20_random_29.txt 26 ms 932 KB
20_random_3.txt 28 ms 924 KB
20_random_30.txt 26 ms 792 KB
20_random_4.txt 29 ms 800 KB
20_random_5.txt 26 ms 928 KB
20_random_6.txt 29 ms 796 KB
20_random_7.txt 25 ms 796 KB
20_random_8.txt 28 ms 840 KB
20_random_9.txt 27 ms 800 KB