Submission #797647

#	Time	Username	Problem	Language	Result	Execution time	Memory
797647		caganyanmaz	Game (IOI14_game)	C++17	100 / 100	279 ms	25200 KiB

game

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

constexpr static int MXSIZE = 1500;
int m[MXSIZE][MXSIZE];
struct Node
{
        int head;
        int tail;
        int size;
        int nxt;
        Node(int index) : head(index), tail(index), size(1), nxt(-1) {}
        Node() : Node(-1) {}
};


Node node[MXSIZE];
int n;

void initialize(int nn)
{
        n = nn;
        for (int i = 0; i < n; i++)
                node[i] = Node(i);
        for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                        m[i][j] = i != j;
}

void merge(int a, int b);

int hasEdge(int u, int v)
{
        u = node[u].head, v = node[v].head;
        if (m[u][v] == 1)
        {
                merge(u, v);
                return 1;
        }
        m[u][v]--;
        m[v][u]--;
        return 0;
}
void merge(int a, int b)
{
        if (node[b].size > node[a].size) swap(a, b);
        for (int i = 0; i < n; i++)
        {
                m[a][i] += m[b][i];
                m[i][a] += m[i][b];
        }
        node[a].size += node[b].size;
        node[node[a].tail].nxt = b;
        node[a].tail = node[b].tail;
        for (; b != -1; b = node[b].nxt)
                node[b].head = a;
}

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