Submission #369153

#	Time	Username	Problem	Language	Result	Execution time	Memory
369153		mjhmjh1104	Game (IOI14_game)	C++14	42 / 100	1083 ms	4960 KiB

game

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

int uf[1506], sz[1506], ds[1506], n;

int _find(int x) {
    if (uf[x] == -1) return x;
    return uf[x] = _find(uf[x]);
}

void _merge(int x, int y) {
    x = _find(x), y = _find(y);
    if (x == y) return;
    sz[y] += sz[x], ds[y] += ds[x], uf[x] = y;
}

vector<pair<int, int>> lt;
int k, idx[1506][1506];

void initialize(int N) {
    n = N;
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
        idx[i][j] = (int)lt.size();
        lt.push_back({ i, j });
    }
}

int hasEdge(int u, int v) {
    if (u > v) swap(u, v);
    swap(lt[idx[u][v]], lt[k]);
    swap(idx[lt[k].first][lt[k].second], idx[lt[idx[u][v]].first][lt[idx[u][v]].second]);
    k++;
    for (int i = 0; i < n; i++) uf[i] = -1;
    for (int i = n * (n - 1) / 2 - 1; i >= k; i--) _merge(lt[i].first, lt[i].second);
    for (int i = 1; i < n; i++) if (_find(i) != _find(0)) return k--, 1;
    return 0;
}

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