Submission #577561

#	Time	Username	Problem	Language	Result	Execution time	Memory
577561		Mazaalai	Game (IOI14_game)	C++17	0 / 100	1 ms	340 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define lb lower_bound
#define LINE "------------\n"
using namespace std;
using PII = pair <int, int>;
const int N = 1500;
set <int> children[N];
set <PII> connections;
int connected[N];
void initialize(int n) {
    for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++) {
        children[i].insert(j);
        children[j].insert(i);
    }
    for (int i = 1; i < n; i++) {
        connected[i]++, connected[i-1]++;
        connections.insert({i-1, i});
    }
}

int hasEdge(int u, int v) {
    // cout << LINE;
    if (u > v) swap(u, v);
    if (!connections.count({u, v})) {
        // cout << "HERE1\n";
        children[u].erase(v);
        children[v].erase(u);
        return 0;
    }
    bool fixed = 0;
    // cout << u << " " << children[u].size() << ' ' << connected[u] << '\n';
    if (children[u].size() - connected[u] > 0) {
        // cout << "OPEN\n";
        if (!fixed) {
            for (auto el : children[u]) {
                int x = el, y = u;
                if (x > y) swap(x, y);
                if (connections.count({x, y})) continue;
                connections.erase(connections.lb({u, v}));
                connections.insert({x, y});
                children[u].erase(v);
                children[v].erase(u);
                connected[u]--, connected[v]--;
                connected[x]++, connected[y]++;
                fixed = 1;
                break;
            }
        }
        if (!fixed) {
            for (auto el : children[v]) {
                int x = el, y = u;
                if (x > y) swap(x, y);
                if (connections.count({x, y})) continue;
                connections.erase(connections.lb({u, v}));
                connections.insert({x, y});
                children[u].erase(v);
                children[v].erase(u);
                connected[u]--, connected[v]--;
                connected[x]++, connected[y]++;
                fixed = 1;
                break;
            }
        }
    }
    return !fixed;
}

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