Submission #1296745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296745		M_W_13	Game (IOI14_game)	C++20	42 / 100	1097 ms	12740 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
const int MAXN = 1507;
set<int> tr[MAXN];
bool odw[MAXN];
int n;

void initialize(int N) {
    n = N;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            tr[i].insert(j);
            tr[j].insert(i);
        }
    }
}

int cnt = 0;

void dfs(int v, int last) {
    cnt++;
    odw[v] = true;
    for (auto syn: tr[v]) {
        if (odw[syn]) continue;
        dfs(syn, v);
    }
}

int hasEdge(int u, int v) {
    tr[u].erase(v);
    tr[v].erase(u);
    cnt = 0;
    rep(i, n) odw[i] = false;
    dfs(0, 0);
    if (cnt != n) {
        tr[u].insert(v);
        tr[v].insert(u);
        return 1;
    }
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 0 / 58