Submission #395152

#	Time	Username	Problem	Language	Result	Execution time	Memory
395152		jeroenodb	Game (IOI14_game)	C++14	0 / 100	1 ms	308 KiB

game

#include "game.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct DSU{
    vector<int> sz,parent, out;
    int components;
    DSU(int n) {
        sz.assign(n,1);
        components = n;
        out.assign(n,n-1);
        parent.resize(n);
        iota(all(parent),0);
    }
    DSU(){}
    void link(int a, int b) {
        components--;
        if(sz[a]<sz[b]) {
            swap(a,b);
        }
        sz[a] = max(sz[a],sz[b]+1);
        out[a] += out[b];
        out[a]-=2;// both directions of this edge are gone
        parent[b] = a;
    }
    bool unite(int a, int b) {
        int pa = find(a),pb = find(b);
        if(pa!=pb) link(pa,pb);
        return pa!=pb;
    }
    int find(int a) {
        if(a==parent[a]) return a;
        return parent[a] = find(parent[a]);
    }
};
DSU dsu;
void initialize(int n) {
    dsu = DSU(n);
}

int hasEdge(int u, int v) {
    int pu = dsu.find(u), pv = dsu.find(v);
    if(dsu.out[pu]==1 or dsu.out[pv]==1) {
        dsu.link(pu,pv);
        return true;
    } else {
        dsu.out[pu]--;
        dsu.out[pv]--;
        return false;
    }
}

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