제출 #711999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711999		thimote75	Game (IOI14_game)	C++14	42 / 100	1087 ms	392 KiB

game

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

using namespace std;

#define graph vector<vector<bool>>

graph n_roads;

bool has_road (int a, int b) {
    return !n_roads[a][b];
}

vector<int> visited;
int stage = 0;
int nbNodes;
bool find (int pos, int target) {
    if (pos == target) return true;
    if (visited[pos] == stage) return false;
    visited[pos] = stage;

    for (int n = 0; n < nbNodes; n ++)
        if (has_road(pos, n) && find(n, target))
            return true;

    return false;
}

void initialize(int n) {
    nbNodes = n;
    n_roads.resize(n, vector<bool>(n, false));
    visited.resize(n, -1);
}

int hasEdge(int u, int v) {
    n_roads[u][v] = true;
    n_roads[v][u] = true;

    stage ++;
    if (find(u, v))
        return 0;
    
    n_roads[u][v] = false;
    n_roads[v][u] = false;

    return 1;
}

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