Submission #968529

#	Time	Username	Problem	Language	Result	Execution time	Memory
968529		Hugo1729	Game (IOI14_game)	C++11	100 / 100	343 ms	27224 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int n;

vector<int> e;
vector<vector<int>> val;

int find(int v){
    if(e[v]<0)return v;
    else{
        e[v]=find(e[v]);
        return e[v];
    }
}

bool same(int x, int y){
    return (find(x)==find(y));
}

int sz(int v){
    return -e[find(v)];
}

void connect(int x, int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(e[x]>e[y])swap(x,y);
    for(int i=0;i<n;i++){
        if(find(i)==i){
            int sus=val[y][i];
            val[y][i]-=sus;
            val[i][y]-=sus;
            val[x][i]+=sus;
            val[i][x]+=sus;
        }
    }
    e[x]+=e[y];
    e[y]=x;
}

void initialize(int s) {
    n=s;
    e.assign(n,-1);
    val.assign(n,vector<int>(n,0));

}

int hasEdge(int u, int v) {
    u=find(u);v=find(v);
    if(u==v)return 1;


    // cout << v << ' ' << u << ' ' << sz(v)*sz(u) << ' ' << val[v][u] << ' ' << val[u][v] << '\n';
    if(sz(v)*sz(u)==val[v][u]+1){
        connect(v,u);
        return 1;
    }else{
        val[v][u]++;
        val[u][v]++;
        return 0;
    }
}

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