제출 #572137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572137		Jesus	게임 (IOI14_game)	C++14	100 / 100	350 ms	25300 KiB

game

#include "game.h"
#include<bits/stdc++.h>

using namespace std;

int ciudades[1501][1501];

int lim=0;

pair<int,int> conexion[1501];

void initialize(int n) {
    lim=n;
    for(int i=0;i<n;i++){
        conexion[i]={i,0};
        for(int j=0;j<n;j++){
            if(i==j) continue;
            ciudades[i][j]=1;
        }
    }
}



int buscar(int nodo){
    if(nodo!=conexion[nodo].first) conexion[nodo].first=buscar(conexion[nodo].first);
    return conexion[nodo].first;
}

void unir(int nodo1,int nodo2){
    conexion[nodo1].second=max(conexion[nodo1].second,conexion[nodo2].second+1);
    conexion[nodo2].first=nodo1;
}



int hasEdge(int u, int v) {
    int pos1=buscar(u);
    int pos2=buscar(v);
    if(ciudades[pos1][pos2]==1){
        ciudades[pos1][pos2]--;
        ciudades[pos2][pos1]--;
        if(conexion[pos2].second<conexion[pos1].second) swap(pos1,pos2);
        for(int i=0;i<lim;i++){
            ciudades[pos1][i]+=ciudades[pos2][i];
            ciudades[pos2][i]=0;
        }
        for(int i=0;i<lim;i++){
            ciudades[i][pos1]+=ciudades[i][pos2];
            ciudades[i][pos2]=0;
        }
        unir(pos1,pos2);
        return 1;
    }
    else{
        ciudades[pos1][pos2]--;
        ciudades[pos2][pos1]--;
        return 0;
    }
}

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