Submission #1023903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023903		borisAngelov	Game (IOI14_game)	C++17	0 / 100	0 ms	348 KiB

game

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

using namespace std;

const int maxn = 1505;

struct DSU
{
    int par[maxn];
    int sz[maxn];

    void init(int n)
    {
        for (int i = 1; i <= n; ++i)
        {
            par[i]= i;
            sz[i] = 1;
        }
    }

    int root(int node)
    {
        if (node == par[node])
        {
            return node;
        }

        return par[node] = root(par[node]);
    }

    void connect(int x, int y)
    {
        x = root(x);
        y = root(y);

        if (x == y)
        {
            return;
        }

        par[y] = x;
        sz[x] += sz[y];
    }

    bool areConnected(int x, int y)
    {
        return root(x) == root(y);
    }
};

DSU dsu;

int n;
int cntQuestions[maxn][maxn];

void initialize(int N)
{
    n = N;
    dsu.init(n);

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

int hasEdge(int u, int v)
{
    ++u;
    ++v;

    int x = dsu.root(u);
    int y = dsu.root(v);

    if (x == y)
    {
        return 1;
    }

    ++cntQuestions[x][y];
    ++cntQuestions[y][x];

    if (cntQuestions[x][y] == dsu.sz[x] * dsu.sz[y])
    {
        dsu.connect(x, y);

        for (int i = 1; i <= n; ++i)
        {
            if (i != x && i != y)
            {
                cntQuestions[x][dsu.root(i)] += cntQuestions[y][dsu.root(i)];
            }
        }

        return 1;
    }
    else
    {
        return 0;
    }
}

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