Submission #436775

#	Time	Username	Problem	Language	Result	Execution time	Memory
436775		Tangent	Game (IOI14_game)	C++17	100 / 100	569 ms	25156 KiB

game

#include "game.h"
#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

int n;
vii parent;
vii above;
vvii possibles;

void initialize(int N) {
    n = N;
    parent.assign(n, -1);
    possibles.assign(n, vii(n, 1));
}

int root(int x) {
    if (parent[x] < 0) return x;
    return parent[x] = root(parent[x]);
}

int hasEdge(int u, int v) {
    if (possibles[root(u)][root(v)] == 1) {
        if (parent[root(u)] < parent[root(v)]) {
            swap(u, v);
        }
        rep(i, n) {
            if (parent[i] < 0 && root(u) != i && root(v) != i) {
                possibles[i][root(v)] += possibles[i][root(u)];
                possibles[root(v)][i] += possibles[i][root(u)];
            }
        }
        parent[root(v)] += parent[root(u)];
        parent[root(u)] = root(v);
        return 1;
    } else {
        possibles[root(u)][root(v)] -= 1;
        possibles[root(v)][root(u)] -= 1;
        return 0;
    }
}

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