Submission #90267

#	Time	Username	Problem	Language	Result	Execution time	Memory
90267		Retro3014	Game (IOI14_game)	C++17	100 / 100	623 ms	159956 KiB

game

#include "game.h"
#include <vector>


using namespace std;
#define MAX_N 1500

int group[MAX_N+1];
bool b[MAX_N+1];
int num[MAX_N+1];
int graph[MAX_N+1][MAX_N+1];

vector<int> v;
int N;

int findg(int x){
    if(group[x]==group[group[x]]){
        return group[x];
    }
    while(x!=group[x]){
        v.push_back(x);
        x=group[x];
    }
    while(!v.empty()){
        group[v.back()]=x;
        v.pop_back();
    }
    return x;
}

bool mrg(int x, int y){
    x=findg(x); y=findg(y);
    if(x==y){
        return false;
    }
    if(graph[x][y]>1){
        graph[x][y]--;
        graph[y][x]--;
        return false;
    }
    if(graph[x][y]==1){
        graph[x][y]--;
        graph[y][x]--;
        if(num[x]>num[y]){
            int tmp=x;x=y;y=tmp;
        }
        group[x]=y;
        num[y]+=num[x];
        b[x]=false;
        for(int i=0; i<N; i++){
            if(b[i]){
                graph[y][i]+=graph[x][i];
                graph[i][y]=graph[y][i];
                graph[x][i]=0;
                graph[i][x]=0;
            }
        }
        return true;
    }
    return false;
}


void initialize(int n) {
    N=n;
    for(int i=0; i<N; i++){
        num[i]=1;
        group[i]=i;
        b[i]=true;
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(i!=j){
                graph[i][j]=1;
            }
        }
    }
}

int hasEdge(int u, int v) {
    return mrg(u, v);
}

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