Submission #1079369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079369		hirayuu_oj	Game (IOI14_game)	C++17	100 / 100	274 ms	25428 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
struct unionfind{
    int sz;
    vector<int> tree;
    unionfind(int size):sz(size),tree(size,-1){}
    int leader(int p){
        if(tree[p]<0)return p;
        int ret=leader(tree[p]);
        tree[p]=ret;
        return ret;
    }
    int size(int p){
        return -tree[leader(p)];
    }
    bool merge(int x,int y){
        x=leader(x);
        y=leader(y);
        if(x==y)return false;
        if(tree[x]>tree[y])swap(x,y);
        tree[x]+=tree[y];
        tree[y]=x;
        return true;
    }
};
vector<vector<int>> edge;
unionfind uni(0);
int N;
void initialize(int n) {
    N=n;
    edge.resize(n,vector<int>(n,0));
    uni=unionfind(n);
}

int hasEdge(int u, int v) {
    u=uni.leader(u);
    v=uni.leader(v);
    assert(u!=v);
    edge[u][v]++;
    edge[v][u]++;
    if(uni.size(u)*uni.size(v)==edge[u][v]){
        uni.merge(u,v);
        if(uni.leader(u)!=u)swap(u,v);
        rep(i,N){
            if(i==u)continue;
            if(i==v)continue;
            edge[i][u]+=edge[i][v];
            edge[u][i]+=edge[v][i];
        }
        return 1;
    }
    return 0;
}

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