Submission #93946

#	Time	Username	Problem	Language	Result	Execution time	Memory
93946		Alexa2001	Game (IOI14_game)	C++17	100 / 100	406 ms	25280 KiB

game

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

using namespace std;

const int Nmax = 1505;

int t[Nmax], bet[Nmax][Nmax], cnt[Nmax], n;

void initialize(int N)
{
    int i; n = N;
    for(i=0; i<N; ++i) t[i] = i, cnt[i] = 1;
}

int boss(int x)
{
    if(x == t[x]) return x;
    return t[x] = boss(t[x]);
}

int hasEdge(int u, int v)
{
    u = boss(u); v = boss(v);
    ++bet[u][v]; ++bet[v][u];

    if(bet[u][v] == cnt[u] * cnt[v])
    {
        t[u] = v;
        cnt[v] += cnt[u];
        for(int i=0; i<n; ++i)
            if(i != u && i != v && t[i] == i)
                bet[i][v] += bet[i][u], bet[v][i] += bet[u][i];
        return 1;
    }
    return 0;
}

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