Submission #103267

#	Time	Username	Problem	Language	Result	Execution time	Memory
103267		naoai	Game (IOI14_game)	C++14	100 / 100	831 ms	20732 KiB

game

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

using namespace std;

const int nmax = 1500;

static int n;
int ok[nmax + 1][nmax + 1];

int gr[nmax + 1], t[nmax + 1];

int findtata (int x) {
    if (x == t[x]) return x;
    return t[x] = findtata(t[x]);
}

void initialize(int N) {
    n = N;
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < n; ++ j) {
            ok[i][j] = 1;
        }
        ok[i][i] = 0;
    }

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

int hasEdge(int u, int v) {
    u = findtata(u), v = findtata(v);

    if (ok[u][v] > 1) {
        -- ok[u][v];
        -- ok[v][u];
        return 0;
    } else {
        if (gr[u] < gr[v])
            swap(u, v);

        for (int i = 0; i < n; ++ i) {
            ok[u][i] += ok[v][i];
            ok[i][u] += ok[i][v];

            ok[v][i] = ok[i][v] = 0;
        }
        ok[u][u] = 0;

        gr[u] += gr[v];
        t[v] = u;

        return 1;
    }
}

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