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 All asi1024 atetubou climpet DEGwer evima flowlight hogloid ichyo math miki_im natsugiri piroz95 semiexp sigma425 sky58 snuke tozangezan wo01 yosupo zerokugi
Score / Max Score 10 / 10 0 / 2 0 / 2 2 / 2 2 / 2 0 / 2 2 / 2 2 / 2 2 / 2 0 / 2 0 / 2 2 / 2 2 / 2 0 / 2 2 / 2 2 / 2 2 / 2 2 / 2 0 / 2 0 / 2 2 / 2
Status
× 33
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
× 1
Set Name Test Cases
All 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 31_asi1024.txt
atetubou 32_atetubou.txt
climpet 33_climpet.txt
DEGwer 34_DEGwer.txt
evima 35_evima.txt
flowlight 36_flowlight.txt
hogloid 37_hogloid.txt
ichyo 38_ichyo.txt
math 39_math.txt
miki_im 40_miki_im.txt
natsugiri 41_natsugiri.txt
piroz95 42_piroz95.txt
semiexp 43_semiexp.txt
sigma425 44_sigma425.txt
sky58 45_sky58.txt
snuke 46_snuke.txt
tozangezan 47_tozangezan.txt
wo01 48_wo01.txt
yosupo 49_yosupo.txt
zerokugi 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