Submission #280180

#	Time	Username	Problem	Language	Result	Execution time	Memory
280180		SamAnd	Game (IOI14_game)	C++17	100 / 100	620 ms	25336 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 1503;

int n;
int p[N];
int q[N][N];

int fi(int x)
{
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}

void initialize(int n)
{
    ::n = n;
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    for (int x = 1; x <= n; ++x)
    {
        for (int y = 1; y <= n; ++y)
        {
            if (x == y)
                continue;
            q[x][y] = 1;
        }
    }
}

int hasEdge(int x, int y)
{
    ++x;
    ++y;
    x = fi(x);
    y = fi(y);
    if (x == y)
        return 0;
    --q[x][y];
    --q[y][x];
    if (q[x][y])
        return 0;
    p[x] = y;

    for (int i = 1; i <= n; ++i)
    {
        q[y][i] += q[x][i];
        q[i][y] += q[x][i];
        q[x][i] = 0;
        q[i][x] = 0;
    }
    return 1;
}

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