Submission #289777

#	Time	Username	Problem	Language	Result	Execution time	Memory
289777		ivan24	Game (IOI14_game)	C++14	100 / 100	561 ms	25468 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

const ll INF = 1e9;

ll max(ll x, ll y){
    return ((x > y) ? x : y);
}
ll min(ll x, ll y){
    return ((x < y) ? x : y);
}

class UnionFind {
private:
    ll n, connected_cnt;
    vi sz,p;
public:
    UnionFind(){}
    UnionFind (ll n): n(n), sz(n,1), p(n), connected_cnt(n){
        for (ll i = 0; n > i; i++) p[i] = i;
    }
    ll root (ll x){
        if (p[x] != x) p[x] = root(p[x]);
        return p[x];
    }
    void unify (ll x, ll y){
        x = root(x), y = root(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x,y);
        p[y] = x; sz[x] += sz[y];
        connected_cnt--;
    }
    ll get_connected_cnt(){
        return connected_cnt;
    }
};

class Solver{
private:
    ll n;
    vvi edgeCnt;
    UnionFind uf;
    void removeEdge(ll u, ll v){
        edgeCnt[u][v]--;
        edgeCnt[v][u]--;
    }
    void mergeComponents (ll u, ll v){
        u = uf.root(u), v = uf.root(v);
        if (edgeCnt[u][v]) return;
        if (u == v) return;

        uf.unify(u,v);
        ll rt = uf.root(v);
        for (ll i = 0; n > i; i++){
            edgeCnt[i][rt] = edgeCnt[i][v]+edgeCnt[i][u];
            edgeCnt[rt][i] = edgeCnt[v][i]+edgeCnt[u][i];
        }
        ll other = u+v-rt;
        for (ll i = 0; n > i; i++){
            edgeCnt[i][other] = 0;
            edgeCnt[other][i] = 0;
        }
    }
public:
    Solver(){}
    Solver(ll n): n (n), edgeCnt(n,vi(n,1)), uf(n){}
    ll hasEdge(ll u, ll v){
        u = uf.root(u), v = uf.root(v);
        if (u == v) return 0;
        removeEdge(u,v);
        if (edgeCnt[u][v]) return 0;
        else{
            mergeComponents(u,v);
            return 1;
        }
    }
};

Solver mySolver;

void initialize(int n) {
    mySolver = Solver(n);
}

int hasEdge(int u, int v) {
    return mySolver.hasEdge(u,v);
}

Compilation message (stderr)

game.cpp: In constructor 'UnionFind::UnionFind(ll)':
game.cpp:25:11: warning: 'UnionFind::p' will be initialized after [-Wreorder]
   25 |     vi sz,p;
      |           ^
game.cpp:24:11: warning:   'll UnionFind::connected_cnt' [-Wreorder]
   24 |     ll n, connected_cnt;
      |           ^~~~~~~~~~~~~
game.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     UnionFind (ll n): n(n), sz(n,1), p(n), connected_cnt(n){
      |     ^~~~~~~~~

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