Submission #282501

#	Time	Username	Problem	Language	Result	Execution time	Memory
282501		Kastanda	Game (IOI14_game)	C++11	100 / 100	567 ms	16124 KiB

game

// M
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
const int N = 1509;
int n, P[N], C[N][N];
void initialize(int _n)
{
        n = _n;
        memset(P, -1, sizeof(P));
}
int Find(int v)
{
        return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        assert(v != u);
        C[v][u] = C[u][v] = 0;
        for (int i = 0; i < n; i ++)
        {
                C[v][i] += C[u][i];
                C[i][v] += C[u][i];
                C[u][i] = C[i][u] = 0;
        }
        P[v] += P[u];
        P[u] = v;
}
int hasEdge(int v, int u)
{
        v = Find(v);
        u = Find(u);
        assert(v != u);
        C[v][u] ++; C[u][v] ++;
        if (C[v][u] == P[v] * P[u])
                return Merge(v, u), 1;
        return 0;
}

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