Submission #1023923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023923		borisAngelov	Game (IOI14_game)	C++17	100 / 100	269 ms	25208 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];

    //cout << u << " -> " << x << endl;
    //cout << v << " -> " << y << endl;
    //cout << "now " << cntQuestions[x][y] << endl;

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

        vector<bool> seen(n + 1, false);

        for (int i = 1; i <= n; ++i)
        {
            int to = dsu.root(i);

            if (to != x && seen[to] == false)
            {
                seen[to] = true;
                cntQuestions[x][to] += cntQuestions[y][to];
                cntQuestions[to][x] = cntQuestions[x][to];
            }
        }

        return 1;
    }
    else
    {
        return 0;
    }
}

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