Submission #711998

#	Time	Username	Problem	Language	Result	Execution time	Memory
711998		thimote75	게임 (IOI14_game)	C++14	42 / 100	1079 ms	756 KiB

game

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

using namespace std;

#define graph vector<set<int>>

graph n_roads;

bool has_road (int a, int b) {
    return a != b && n_roads[a].find(b) == n_roads[a].end();
}

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);
    visited.resize(n, -1);
}

int hasEdge(int u, int v) {
    n_roads[u].insert(v);
    n_roads[v].insert(u);

    stage ++;
    if (find(u, v))
        return 0;
    
    n_roads[u].erase(v);
    n_roads[v].erase(u);

    return 1;
}

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