Submission #252490

#	Time	Username	Problem	Language	Result	Execution time	Memory
252490		eohomegrownapps	Game (IOI14_game)	C++14	15 / 100	1 ms	384 KiB

game

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

vector<vector<int>> adjmat;
vector<int> ufds;
vector<int> usize;
int root(int i){
    if (ufds[i]==i){
        return i;
    } else {
        return ufds[i]=root(ufds[i]);
    }
}

void connect(int a, int b){
    int ra = root(a);
    int rb = root(b);
    if (ra==rb){return;}
    //path compression
    ufds[ra]=rb;
    usize[rb]+=usize[ra];
}

int n;
//0 - no, 1 - yes, 2 - unchecked
void initialize(int N) {
    n=N;
    adjmat.resize(n,vector<int>(n,2));
    ufds.resize(n);
    usize.resize(n,1);
    for (int i = 0; i<n; i++){
        ufds[i]=i;
    }
}

int hasEdge(int u, int v) {
    //check neighbours of u
    //cout<<u<<" "<<v<<'\n';
    for (int i = 0; i<n; i++){
        if (i==u||i==v){continue;}
        if (adjmat[u][i]==1){
            //cout<<"neighbour "<<i<<'\n';
            if (adjmat[i][v]==2){
                //must put 0
                adjmat[u][v]=0;
                adjmat[v][u]=0;
                return 0;
            }
        }
        if (adjmat[v][i]==1){
            //cout<<"neighbour "<<i<<'\n';
            if (adjmat[i][u]==2){
                //must put 0
                adjmat[u][v]=0;
                adjmat[v][u]=0;
                return 0;
            }
        }
    }
    if (usize[root(u)]+usize[root(v)]==n){
        return 0;
    }
    adjmat[u][v]=1;
    adjmat[v][u]=1;
    connect(u,v);
    return 1;
}

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