제출 #153702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153702		dennisstar	게임 (IOI14_game)	C++11	100 / 100	514 ms	25548 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int clr[1550];
int chk[1550][1550];

int fcnt, ucnt, n;

void Union(int a, int b) {
	ucnt--;
	for (int i=0; i<n; i++) {if (clr[i]==b) clr[i]=a;}
	for (int i=0; i<n; i++) chk[a][i]+=chk[b][i];
	for (int i=0; i<n; i++) chk[i][a]+=chk[i][b];
}

void initialize(int n_) {
	n=n_;
	ucnt=n; fcnt=0;
	for (int i=0; i<n; i++) {clr[i]=i;}
	for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (i!=j) chk[i][j]=1;
}

int hasEdge(int u, int v) {
	fcnt++;
	if (ucnt==2) return 0;
	u=clr[u]; v=clr[v];
	if (u==v) {
		return 1;
	}
	if (chk[u][v]==1) {
		Union(u, v);
		return 1;
	} 
	else {
		chk[u][v]--; chk[v][u]--;
		return 0;
	}
}

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