Submission #1125822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125822		makmed1337	Game (IOI14_game)	C++20	100 / 100	346 ms	15936 KiB

game

#include "game.h"
#include <vector>
using namespace std;

namespace solution_ns {
int n;
vector<int> a;
vector<vector<int>> lca;
void build(int i, int l, int r) {
    if (l == r)
        return;

    int m = (l + r) / 2;
    build(2 * i, l, m);
    build(2 * i + 1, m + 1, r);
    for (int x = l; x <= m; x++)
        for (int y = m + 1; y <= r; y++)
            lca[x][y] = lca[y][x] = i;
}
}; // namespace solution_ns

void initialize(int n) {
    using namespace solution_ns;
    solution_ns::n = n;
    a.assign(4 * n, 0);
    lca.assign(n, vector<int>(n));
    build(1, 0, n - 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            a[lca[i][j]]++;
}

int hasEdge(int u, int v) {
    using namespace solution_ns;

    int l = lca[u][v];
    if (a[l] == 1)
        return 1;
    a[l]--;
    return 0;
}

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