Submission #114720

#	Time	Username	Problem	Language	Result	Execution time	Memory
114720		toonewbie	Game (IOI14_game)	C++17	100 / 100	914 ms	29208 KiB

game

#pragma GCC optimize("Ofast")
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1555;

int n;
vector <int> g[N];
int has[N][N];
void initialize(int N) {
    n = N;
    memset(has, -1, sizeof(has));
    for (int i = 1; i <= n; i++) {
        has[i][i] = 1;
        g[i].push_back(i);
    }
}

int hasEdge(int u, int v) {
    u++, v++;
    int x = g[u].size(), y = g[v].size(), a, b, i, j, ii, jj;
    for (ii = 0; ii < x; ii++) {
        for (jj = 0; jj < y; jj++) {
            i = g[u][ii], j = g[v][jj];
            if (i == u && j == v) continue;
            if (has[i][j] == -1) {
                return has[u][v] = has[v][u] = 0;
            }
        }
    }
    for (i = 0; i < x; i++) {
        for (j = 0; j < y; j++) {
            a = g[u][i], b = g[v][j];
            if (has[a][b] != 1) {
                has[a][b] = has[b][a] = 1;
                g[a].push_back(b);
                g[b].push_back(a);
            }
        }
    }
    return 1;
}

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