Submission #1822951


Source Code Expand

Copy
#include <cstdio>
#include <functional>
#include <vector>
#include <sys/signal.h>
#include <sys/time.h>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

int result = 0;
void maximum_independent_set(vector<vector<int> > const & g) {
    int n = g.size();
    vector<bool> used(n);
    function<void (int, int)> dfs = [&](int i, int acc) {
        setmax(result, acc);
        if (i == n) return;
        if (used[i]) { dfs(i + 1, acc); return; }
        used[i] = true;
        vector<bool> preserved = used;
        for (int j : g[i]) used[j] = true;
        dfs(i + 1, acc + 1);
        used = preserved;
        if (g[i].size() >= 2) dfs(i + 1, acc);
        used[i] = false;
    };
    dfs(0, 0);
}

void handler(int) {
    // output
    printf("%d\n", result);
    exit(EXIT_SUCCESS);
}
int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(n);
    repeat (i, m) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    // solve
    signal(SIGALRM, handler);
    itimerval tv;
    tv.it_value.tv_sec = 1;
    tv.it_value.tv_usec = 800 * 1000;
    tv.it_interval = {};
    setitimer(ITIMER_REAL, &tv, NULL);
    maximum_independent_set(g);
    raise(SIGALRM);
    return 0;
}

Submission Info

Submission Time
Task G - Mixture Drug
User kimiyuki
Language C++14 (Clang 3.8.0)
Score 0
Code Size 1438 Byte
Status CE

Compile Error

./Main.cpp:32:10: error: use of undeclared identifier 'EXIT_SUCCESS'
    exit(EXIT_SUCCESS);
         ^
1 error generated.