제출 #577560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577560		Mazaalai	게임 (IOI14_game)	C++17	0 / 100	1 ms	388 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";
        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;
        }
    }
    return !fixed;
}

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