제출 #1155912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155912		an22inkle	게임 (IOI14_game)	C++20	42 / 100	1096 ms	12616 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using paira = array<int, 2>;
using ll = long long;


/*
Main idea : Do not reveal a connection between two componenets until all other possible connections are asked

Solution 1 : naive DFS

We maintain a mayb graph. Remove an edge from this maybe graph if we answer for that edge.

To check if we are on the "last" edge for two componenets, we prematurely remove that edge and then check if the maybe graph is still connnected.
if the graph is still connected we can safely answer no

*/

int N = 2;
vector<set<int>> maybe(N, set<int>());

void initialize(int n) {
    N = n;
    maybe.resize(n);

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            maybe[i].insert(j);
            maybe[j].insert(i);
        }
    }
}

int hasEdge(int u, int v) {
    maybe[u].erase(v);
    maybe[v].erase(u);

    vector<bool> vis(N);
    function<void(int)> dfs = [&](int u) {
        if (vis[u]) return;
        vis[u] = 1;
        for (int v : maybe[u]) {
            dfs(v);
        }
    };

    dfs(u);

    if (vis[v]) {
        return 0;
    } else {
        return 1;
    }
}

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