Submission #655104

#	Time	Username	Problem	Language	Result	Execution time	Memory
655104		jophyyjh	Game (IOI14_game)	C++14	42 / 100	1089 ms	1616 KiB

game

/**
 * A pretty straight-forward problem. The problem asks us to "confuse" the player by
 * only letting him/her know the graph's connectivity at the very last moment.
 * 
 * In order to be "between" connected and disconnected, it makes sense to have a
 * small (~O(n)) number of edges. Moreover, whether each edge is present shall be
 * determined by what edges are actually asked by the player. Here's my solution:
 *    First imagine that all edges have the state "undecided". At the beginning,
 *    all edges are "by default" present (we'll find out the actual ans when
 *    the player asks for it). When the player asks for a new edge {u,v}, we
 *    see whether not including {u,v} makes the graph disconnected, assuming
 *    that all "undecided" edges are included.
 *    If it does, we must include {u,v}; otherwise, we exclude it from the
 *    graph since there're other undecided edges that preserve connectivity.
 *    Finally, we flag the edge as "decided".
 * One can prove by induction that nC2 queries are required before we can determine
 * connectivity.
 * 
 * Time Complexity: O(n^2)
 * Implementation 1         (connectivity)
*/

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

typedef std::vector<int>    vec;


int n;
std::vector<vec> graph;     // -1: undecided, 0: not included, 1: present

void initialize(int _n) {
    n = _n;
    graph.assign(n, vec(n, -1));
}


bool connected() {
    std::vector<bool> visited(n, false);
    visited[0] = true;
    std::queue<int> bfs_queue;
    bfs_queue.emplace(0);
    int non_visited = n;
    while (!bfs_queue.empty()) {
        int t = bfs_queue.front();
        bfs_queue.pop();
        non_visited--;
        for (int neighb = 0; neighb < n; neighb++) {
            if (!visited[neighb] && graph[neighb][t] != 0) {
                visited[neighb] = true;
                bfs_queue.emplace(neighb);
            }
        }
    }
    return non_visited == 0;
}

int hasEdge(int u, int v) {
    if (graph[u][v] == -1) {
        graph[u][v] = graph[v][u] = 0;
        if (!connected())
            graph[u][v] = graph[v][u] = 1;
    }
    return graph[u][v];
}

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