Submission #260656

#	Time	Username	Problem	Language	Result	Execution time	Memory
260656		A02	Game (IOI14_game)	C++14	100 / 100	557 ms	25336 KiB

game

#include "game.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

using namespace std;

vector<int> components;
vector<vector<int> > component_unknown_edges;
int N;

void initialize(int n) {

    N = n;

    components = vector<int> (n, 0);

    for (int i = 0; i < n; i++){
        components[i] = i;
    }

    component_unknown_edges = vector<vector<int> > (n, vector<int> (n, 0));

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

int hasEdge(int u, int v) {

    if (components[u] == components[v]){
        return 0;
    }

    int c1 = components[u];
    int c2 = components[v];

//    cout << u << "vertices" << v << endl;
//    cout << c1 << ' ' << c2 << endl;
//    cout << component_unknown_edges[c1][c2] << endl;
//    cout << component_unknown_edges[0][3] << ' ' << component_unknown_edges[3][0] << endl;

    if (component_unknown_edges[c1][c2] > 1){
        component_unknown_edges[c1][c2]--;
        component_unknown_edges[c2][c1]--;
        return 0;
    }


    for (int i = 0; i < N; i++){
        if (components[i] == c2){
            components[i] = c1;
        }
    }

    for (int i = 0; i < N; i++){
        if (i != c1){
            component_unknown_edges[c1][i] += component_unknown_edges[c2][i];
            component_unknown_edges[i][c1] = component_unknown_edges[c1][i];
        }
    }

    return 1;
}

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