Submission #297682

#	Time	Username	Problem	Language	Result	Execution time	Memory
297682		juckter	Game (IOI14_game)	C++14	100 / 100	544 ms	20472 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> sz, rep, act;
vector<vector<int>> used;
int N;

int find(int x) {
    return rep[x] == x ? x : rep[x] = find(rep[x]);
}

void join(int u, int v) {
    if(sz[u] < sz[v])
        swap(u, v);
    for(int i = 0; i < N; i++) {
        used[u][i] += used[v][i];
        used[i][u] += used[i][v];
    }
    sz[u] += sz[v];
    rep[v] = u;
}

void initialize(int n) {
    N = n;
    rep.resize(n);
    sz.resize(n, 1);
    used.resize(n, vector<int>(n));
    iota(rep.begin(), rep.end(), 0);
}

int hasEdge(int u, int v) {
    u = find(u);
    v = find(v);
    if(u == v)
        return 0;
    if(used[u][v] != sz[u] * sz[v] - 1) {
        used[u][v]++;
        used[v][u]++;
        return 0;
    }
    else {
        join(u, v);
        return 1;
    }
}

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