Submission #52156

#	Time	Username	Problem	Language	Result	Execution time	Memory
52156		aquablitz11	Game (IOI14_game)	C++14	15 / 100	3 ms	868 KiB

game

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

const int N = 1510;
int n, G[N][N], vis[N], r, c[N];

void initialize(int n)
{
    ::n = n;
    r = n*(n-1)/2;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j)
                G[i][j] = 1;
        }
    }
}

void dfs(int u)
{
    vis[u] = true;
    for (int v = 0; v < n; ++v) {
        if (!vis[v] && G[u][v] == 1)
            dfs(v);
    }
}

int hasEdge(int u, int v)
{
    if (r-- <= n-1) {
        for (int i = 0; i < n; ++i) vis[i] = false;
        G[u][v] = G[v][u] = 0;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (!vis[i]) {
                ++cnt;
                if (cnt > 1)
                    break;
                dfs(i);
            }
        }
        if (cnt > 1)
            return G[u][v] = G[v][u] = 1;
        return 0;
    } else {
        ++c[u], ++c[v];
        if (c[u] == n-1 || c[v] == n-1)
            return 1;
        return G[u][v] = G[v][u] = 0;
    }
}

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