Submission #486410


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;
        int mx = 0, V = -1;
        rep(u, n) if (exists[u]) {
            if (deg[u] < mn) mn = deg[u], v = u;
            if (deg[v] > mx) mx = deg[u], V = u;
        }
        if (v == -1) {
            ret.push_back(cur);
        } else if (mx >= 6) {
            select(V), dfs(), unselect(V);
            for (int nv : G[V]) {
                if (exists[nv]) select(nv), dfs(), unselect(nv);
            }
        } 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 34
Code Size 3735 Byte
Status
Exec Time 2078 ms
Memory 425404 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
asi1024 0 / 2 31_asi1024.txt
atetubou 0 / 2 32_atetubou.txt
climpet 2 / 2 33_climpet.txt
DEGwer 2 / 2 34_DEGwer.txt
evima 0 / 2 35_evima.txt
flowlight 2 / 2 36_flowlight.txt
hogloid 2 / 2 37_hogloid.txt
ichyo 2 / 2 38_ichyo.txt
math 0 / 2 39_math.txt
miki_im 0 / 2 40_miki_im.txt
natsugiri 2 / 2 41_natsugiri.txt
piroz95 2 / 2 42_piroz95.txt
semiexp 0 / 2 43_semiexp.txt
sigma425 2 / 2 44_sigma425.txt
sky58 2 / 2 45_sky58.txt
snuke 2 / 2 46_snuke.txt
tozangezan 2 / 2 47_tozangezan.txt
wo01 0 / 2 48_wo01.txt
yosupo 0 / 2 49_yosupo.txt
zerokugi 2 / 2 50_zerokugi.txt
Case Name Status Exec Time Memory
00_sample_1.txt 24 ms 796 KB
00_sample_2.txt 27 ms 800 KB
00_sample_3.txt 26 ms 924 KB
20_random_1.txt 26 ms 928 KB
20_random_10.txt 26 ms 736 KB
20_random_11.txt 26 ms 924 KB
20_random_12.txt 26 ms 924 KB
20_random_13.txt 24 ms 932 KB
20_random_14.txt 25 ms 928 KB
20_random_15.txt 23 ms 924 KB
20_random_16.txt 26 ms 736 KB
20_random_17.txt 25 ms 924 KB
20_random_18.txt 25 ms 920 KB
20_random_19.txt 25 ms 928 KB
20_random_2.txt 29 ms 924 KB
20_random_20.txt 26 ms 804 KB
20_random_21.txt 26 ms 796 KB
20_random_22.txt 24 ms 796 KB
20_random_23.txt 26 ms 928 KB
20_random_24.txt 25 ms 928 KB
20_random_25.txt 26 ms 804 KB
20_random_26.txt 24 ms 796 KB
20_random_27.txt 25 ms 724 KB
20_random_28.txt 26 ms 924 KB
20_random_29.txt 26 ms 804 KB
20_random_3.txt 26 ms 916 KB
20_random_30.txt 26 ms 804 KB
20_random_4.txt 33 ms 920 KB
20_random_5.txt 26 ms 928 KB
20_random_6.txt 25 ms 924 KB
20_random_7.txt 28 ms 912 KB
20_random_8.txt 26 ms 804 KB
20_random_9.txt 24 ms 924 KB
31_asi1024.txt 2055 ms 168760 KB
32_atetubou.txt 2074 ms 365888 KB
33_climpet.txt 25 ms 920 KB
34_DEGwer.txt 262 ms 8012 KB
35_evima.txt 2060 ms 234308 KB
36_flowlight.txt 1018 ms 99268 KB
37_hogloid.txt 56 ms 2728 KB
38_ichyo.txt 197 ms 40144 KB
39_math.txt 2064 ms 311240 KB
40_miki_im.txt 2078 ms 425404 KB
41_natsugiri.txt 33 ms 924 KB
42_piroz95.txt 30 ms 804 KB
43_semiexp.txt 2043 ms 74180 KB
44_sigma425.txt 24 ms 800 KB
45_sky58.txt 25 ms 804 KB
46_snuke.txt 31 ms 916 KB
47_tozangezan.txt 1514 ms 51660 KB
48_wo01.txt 2061 ms 284484 KB
49_yosupo.txt 2055 ms 190144 KB
50_zerokugi.txt 78 ms 1956 KB