Submission #1108497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108497		Ariadna	Game (IOI14_game)	C++14	42 / 100	1077 ms	10728 KiB

game

#include <bits/stdc++.h>
#define fi first 
#define se second
using namespace std;
 
int n;
vector<vector<int>> adj;
vector<unordered_set<int>> unknown;
 
void initialize(int N) {
    n = N;
    adj = vector<vector<int>>(n);
    unknown = vector<unordered_set<int>>(n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j != i) unknown[i].insert(j);
        }
    }
}

void dfs(int u, vector<bool>& visited) {
    visited[u] = true;
    for (int v: adj[u]) {
        if (!visited[v]) dfs(v, visited);
    }
    for (int v: unknown[u]) {
        if (!visited[v]) dfs(v, visited);
    }
}

bool connected(int u, int v) {
    vector<bool> visited(n, false);
    dfs(u, visited);
    return visited[v];
}
 
int hasEdge(int u, int v) {
    unknown[u].erase(v);
    unknown[v].erase(u);
    if (!connected(u, v)) {
        adj[u].push_back(v);
        adj[v].push_back(u);
        return 1;
    }
    return 0;
}

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