Submission #1036963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036963		vanea	Game (IOI14_game)	C++14	42 / 100	1066 ms	6892 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;

const int mxN = 2e3+10;

vector<int> adj[mxN];
int n;
bool blocked[mxN][mxN];
bool vis[mxN];

int dfs(int node) {
    vis[node] = true;
    int cnt = 1;
    for(auto it : adj[node]) {
        if(blocked[node][it]) continue;
        if(!vis[it]) cnt += dfs(it);
    }
    return cnt;
}

int hasEdge(int u, int v) {
    memset(vis, false, sizeof vis);
    blocked[u][v] = blocked[v][u] = true;
    int cnt = dfs(0);
    if(cnt != n) {
        blocked[u][v] = blocked[v][u] = false;
        return 1;
    }
    return 0;
}

void initialize(int N) {
    n = N;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            adj[i].push_back(j);
            adj[j].push_back(i);
        }
    }
}
/*
int main()
{
    initialize(4);
    cout << hasEdge(0, 1) << hasEdge(3, 0) << hasEdge(1, 2) << hasEdge(0, 2);
    cout << hasEdge(3, 1) << hasEdge(2, 3);
}*/

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