Submission #381638

#	Time	Username	Problem	Language	Result	Execution time	Memory
381638		vishesh312	Game (IOI14_game)	C++17	15 / 100	2 ms	512 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 (u < v) swap(u, v);
    if (cnt[u][v] < siz[u] * siz[v] - 1) {
        ++cnt[u][v];
        return 0;
    }
    siz[u] += siz[v];
    link[v] = u;
    for (int i = 0; i < u; ++i) cnt[u][i] += cnt[v][i];
    for (int i = u+1; i < n; ++i) cnt[i][u] += cnt[i][v];
    return 1;
}

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