Submission #791813

#	Time	Username	Problem	Language	Result	Execution time	Memory
791813		caganyanmaz	Game (IOI14_game)	C++14	0 / 100	1 ms	340 KiB

game

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



struct Node
{
        int head;
        int tail;
        int size;
        int rcount;
        int nxt;
        Node(int index) : head(index), tail(index), size(1), rcount(0), nxt(-1) {}
        Node() : Node(-1) {}
};

constexpr static int MXSIZE = 1500;
int ans[MXSIZE][MXSIZE];
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++)
                        ans[i][j] = -1;
}


bool needs_friends(int i)
{
        return (n-node[i].size) * node[i].size == node[i].rcount + 1;
}

void merge(int a, int b)
{
        if (node[a].size < node[b].size) swap(a, b);
        node[a].size += node[b].size;
        node[a].rcount += node[b].rcount;
        node[node[a].tail].nxt = b;
        node[a].tail = node[b].tail;
        for (int i = b; i != -1; i = node[i].nxt)
        {
                for (int j = a; j != -1; j = node[j].nxt)
                        if (ans[min(i,j)][max(i,j)] == 0)
                                node[a].rcount--;
                node[i].head = a;
        }
}

int hasEdge(int u, int v)
{
        if (u > v) swap(u, v);
        if ((ans[u][v] == -1) && (node[u].head != node[v].head) && (needs_friends(node[u].head) || needs_friends(node[v].head)))
        {
                merge(node[u].head, node[v].head);
                ans[u][v] = 1;
        }
        else if (ans[u][v] == -1)
        {
                if (node[u].head != node[v].head)
                {
                        node[node[u].head].rcount++;
                        node[node[v].head].rcount++;
                }
                ans[u][v] = 0;
        }
        return ans[u][v];
}

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