Submission #106202

#	Time	Username	Problem	Language	Result	Execution time	Memory
106202		popovicirobert	Game (IOI14_game)	C++14	100 / 100	592 ms	25544 KiB

game

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

using namespace std;

struct DSU {
    vector <int> par, sz;
    int n;
    inline void init(int _n) {
        n = _n;
        par.resize(n, -1), sz.resize(n, 1);
    }
    int root(int x) {
        if(par[x] == -1)
            return x;
        return par[x] = root(par[x]);
    }
    inline void join(int x, int y) {
        x = root(x), y = root(y);
        if(x != y) {
            par[x] = y;
            sz[y] += sz[x];
        }
    }
}dsu;

static int N;
vector < vector <int> > cnt;
vector <int> vis;
int now;

void initialize(int n) {
    N = n;
    dsu.init(N); vis.resize(N);
    cnt.resize(N, vector <int>(N));
}

int hasEdge(int u, int v) {
    u = dsu.root(u), v = dsu.root(v);
    if(u == v) {
        return 0;
    }
    if(cnt[u][v] + 1 == dsu.sz[u] * dsu.sz[v]) {
        now++;
        for(int i = 0; i < N; i++) {
            int cur = dsu.root(i);
            if(vis[cur] == now) {
                continue;
            }
            vis[cur] = now;
            if(cur != u && cur != v) {
                cnt[cur][v] += cnt[cur][u];
                cnt[v][cur] += cnt[cur][u];
            }
        }
        dsu.join(u, v);
        return 1;
    }
    else {
        cnt[u][v]++, cnt[v][u]++;
        return 0;
    }
}

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