Submission #287201

#	Time	Username	Problem	Language	Result	Execution time	Memory
287201		Marte	Game (IOI14_game)	C++17	15 / 100	4 ms	768 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1500;
int parents[N];
set<pair<int, int>> links[N];

int find(int v) {
    if (v == parents[v])
        return v;
    return parents[v] = find(parents[v]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b)
        parents[b] = a;
}

void initialize(int n) {
    for (int i = 0; i < n; ++i) {
        parents[i] = i;
        for (int j = 0; j < n; ++j) {
            if (i != j)
                links[i].emplace(i, j);
        }
    }
}

int hasEdge(int u, int v) {
    int c1 = find(u);
    int c2 = find(v);
    if (c1 == c2)
        return 1;
    links[c1].erase({u, v});
    links[c2].erase({v, u});
    queue<int> q({c1, c2});
    while (!q.empty()) {
        int c = find(q.front());
        q.pop();
        if (links[c].size() == 1) {
            int self, other;
            tie(self, other) = *links[c].begin();
            int other_c = find(other);
            merge(c, other_c);
            links[other_c].erase({other, self});
            links[c] = move(links[other_c]);
            q.emplace(other_c);
        }
    }
    return 0;
}

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