Submission #486763


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, k;
    const graph& G;
    vector<int> ret, 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);
        }
    }
    bool 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) {
            if (ret.size() < cur.size()) {
                ret = cur;
                return int(cur.size()) >= k;
            }
        } else if (mx >= 6) {
            select(V), dfs(), unselect(V);
            for (int nv : G[V]) {
                if (exists[nv]) {
                    select(nv);
                    if (dfs()) return true;
                    unselect(nv);
                }
            }
        } else {
            select(v), dfs(), unselect(v);
            for (int nv : G[v]) {
                if (exists[nv]) {
                    select(nv);
                    if (dfs()) return true;
                    unselect(nv);
                }
            }
        }
        return false;
    }
public:
    maximal_indsets(const graph& G, int k) : n(G.size()), k(k), G(G), exists(n, true), deg(n), block(n) {
        rep(v, n) deg[v] = G[v].size();
        dfs();
    }
    const 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]);
            }
        }
        vector<int> res = maximal_indsets(Gsub, k - int(ans.size())).get();
        for (int v : res) {
            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 3769 Byte
Status
Exec Time 2034 ms
Memory 936 KB

Judge Result

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 26 ms 808 KB
00_sample_2.txt 24 ms 792 KB
00_sample_3.txt 23 ms 928 KB
20_random_1.txt 25 ms 932 KB
20_random_10.txt 23 ms 928 KB
20_random_11.txt 26 ms 920 KB
20_random_12.txt 25 ms 800 KB
20_random_13.txt 25 ms 928 KB
20_random_14.txt 26 ms 796 KB
20_random_15.txt 25 ms 928 KB
20_random_16.txt 25 ms 924 KB
20_random_17.txt 25 ms 924 KB
20_random_18.txt 27 ms 800 KB
20_random_19.txt 25 ms 928 KB
20_random_2.txt 26 ms 924 KB
20_random_20.txt 25 ms 736 KB
20_random_21.txt 26 ms 920 KB
20_random_22.txt 27 ms 804 KB
20_random_23.txt 27 ms 800 KB
20_random_24.txt 26 ms 816 KB
20_random_25.txt 27 ms 804 KB
20_random_26.txt 26 ms 800 KB
20_random_27.txt 26 ms 932 KB
20_random_28.txt 29 ms 804 KB
20_random_29.txt 27 ms 792 KB
20_random_3.txt 26 ms 792 KB
20_random_30.txt 27 ms 928 KB
20_random_4.txt 26 ms 920 KB
20_random_5.txt 26 ms 928 KB
20_random_6.txt 25 ms 920 KB
20_random_7.txt 25 ms 804 KB
20_random_8.txt 27 ms 924 KB
20_random_9.txt 26 ms 800 KB
31_asi1024.txt 2033 ms 920 KB
32_atetubou.txt 2034 ms 928 KB
33_climpet.txt 25 ms 920 KB
34_DEGwer.txt 238 ms 928 KB
35_evima.txt 2034 ms 932 KB
36_flowlight.txt 652 ms 800 KB
37_hogloid.txt 52 ms 800 KB
38_ichyo.txt 73 ms 724 KB
39_math.txt 2034 ms 936 KB
40_miki_im.txt 2032 ms 924 KB
41_natsugiri.txt 30 ms 804 KB
42_piroz95.txt 29 ms 800 KB
43_semiexp.txt 2033 ms 932 KB
44_sigma425.txt 24 ms 804 KB
45_sky58.txt 27 ms 812 KB
46_snuke.txt 30 ms 932 KB
47_tozangezan.txt 1307 ms 928 KB
48_wo01.txt 2034 ms 936 KB
49_yosupo.txt 2033 ms 932 KB
50_zerokugi.txt 67 ms 792 KB