Submission #289765

#	Time	Username	Problem	Language	Result	Execution time	Memory
289765		ivan24	Game (IOI14_game)	C++14	42 / 100	1053 ms	1656 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 adjMatrix;
    UnionFind uf;
    bool isUnited(){
        queue<ll> q;
        vi isVisited(n,0);
        q.push(0); isVisited[0] = 1;
        while (!q.empty()){
            ll v = q.front(); q.pop();
            for (ll i = 0; n > i; i++){
                if (adjMatrix[v][i] && !isVisited[i]){
                    isVisited[i] = 1; q.push(i);
                }
            }
        }
        for (ll i = 0; n > i; i++)
            if (!isVisited[i]) return false;
        return true;
    }
    void setEdge(ll u, ll v, ll val){
        adjMatrix[u][v] = val;
        adjMatrix[v][u] = val;
    }
public:
    Solver(){}
    Solver(ll n): n (n), adjMatrix(n,vi(n,-1)){
        uf = UnionFind(n);
    }
    ll hasEdge(ll u, ll v){
        setEdge(u,v,0);
        if (!isUnited()){
            setEdge(u,v,1);
            return 1;
        }else return 0;
    }
};

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: 0 / 58