Submission #1049360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049360		ArthuroWich	Game (IOI14_game)	C++17	0 / 100	1 ms	348 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
int p[1505];
set<pair<int, int>> st[1505];
int find(int x) {
    if (p[x] == x) {
        return x;
    }
    p[x] = find(p[x]);
    return p[x];
}
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) {
        return;
    }
    p[b] = a;
}
void initialize(int n) {
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            st[i].insert({i, j});
            st[j].insert({i, j});
        }
    }
}
int hasEdge(int u, int v) {
    int a = u, b = v;
    u = min(a, b);
    v = max(a, b);
    set<pair<int, int>> todel;
    for (auto [p, q] : st[u]) {
        if (find(p) == find(q)) {
            todel.insert({p, q});
        }
    }
    for (auto p : todel) {
        st[u].erase(p);
    }
    todel.clear();
    for (auto [p, q] : st[v]) {
        if (find(p) == find(q)) {
            todel.insert({p, q});
        }
    }
    for (auto p : todel) {
        st[v].erase(p);
    }
    if (st[u].empty() || st[v].empty() || find(u) == find(v)) {
        return 0;
    }
    if (st[u].size() < 3 || st[v].size() < 3) {
        st[u].erase({u, v});
        st[v].erase({u, v});
        merge(u, v);
        return 1;
    }
    st[u].erase({u, v});
    st[v].erase({u, v});
    return 0;
}

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