Submission #252511

#	Time	Username	Problem	Language	Result	Execution time	Memory
252511		eohomegrownapps	Game (IOI14_game)	C++14	100 / 100	583 ms	34068 KiB

game

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

int adjmat[1500][1500];
int numnotconn[1500][1500];
int ufds[1500];
int usize[1500];
int n;
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];
    //new root: rb
    for (int i = 0; i<n; i++){
        numnotconn[rb][i]+=numnotconn[ra][i];
        numnotconn[i][rb]+=numnotconn[i][ra];
    }
}

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

void ret0(int u, int v, int ru, int rv){
    adjmat[u][v]=0;
    adjmat[v][u]=0;
    numnotconn[ru][rv]++;
    numnotconn[rv][ru]++;
}

void ret1(int u, int v, int ru, int rv){
    adjmat[u][v]=1;
    adjmat[v][u]=1;
    connect(u,v);
}

int hasEdge(int u, int v) {
    int ru = root(u);
    int rv = root(v);
    if (ru==rv){
        ret1(u,v,ru,rv);
        return 1;
    }
    //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
                ret0(u,v,ru,rv);
                return 0;
            }
        }
        if (adjmat[v][i]==1){
            //cout<<"neighbour "<<i<<'\n';
            if (adjmat[i][u]==2){
                //must put 0
                ret0(u,v,ru,rv);
                return 0;
            }
        }
    }*/
    if (usize[ru]+usize[rv]==n){
        ret0(u,v,ru,rv);
        return 0;
    }
    if (numnotconn[ru][rv]==(usize[ru]*usize[rv]-1)){
        ret1(u,v,ru,rv);
        return 1;
    }
    ret0(u,v,ru,rv);
    return 0;
}

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