제출 #381641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
381641		vishesh312	게임 (IOI14_game)	C++17	100 / 100	507 ms	16056 KiB

game

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

using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

using ll = long long;
const int mod = 1e9+7;

vector<int> siz, link;
int n;
vector<vector<int>> cnt;

void initialize(int _n) {
    n = _n;
    siz.resize(n, 1);
    link.resize(n);
    for (int i = 0; i < n; ++i) link[i] = i;
    cnt.resize(n);
    for (auto &x : cnt) x.resize(n);
}

int find(int x) {
    while (link[x] != x) x = link[x];
    return x;
}

bool same(int a, int b) {
    return find(a) == find(b);
}

int hasEdge(int u, int v) {
    u = find(u);
    v = find(v);
    if (same(u, v)) {
        return 1;
    }
    if (cnt[u][v] < siz[u] * siz[v] - 1) {
        ++cnt[u][v], ++cnt[v][u];
        return 0;
    }
    if (siz[u] < siz[v]) swap(u, v);
    siz[u] += siz[v];
    link[v] = u;
    for (int i = 0; i < n; ++i) {
        cnt[u][i] += cnt[v][i];
        cnt[i][u] += cnt[v][i];
    }
    return 1;
}

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