제출 #133243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133243		sealnot123	게임 (IOI14_game)	C++14	42 / 100	1077 ms	3620 KiB

game

#include "game.h"

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 1505;

int g[N][N];
int mk[N];
int nn;
queue<int> bfs;

bool chek(int n){
	memset(mk, 0, sizeof mk);
	int cnt = 1, i;
	bfs.push(0);
	mk[0] = 1;
	while(!bfs.empty()){
		int u = bfs.front();
		bfs.pop();
		for(i = 0; i < n; i++){
			if(!g[u][i] || mk[i]) continue;
			cnt++; mk[i] = 1;
			bfs.push(i);
		}
	}
	/*printf("%d\n",cnt);*/
	return cnt == n;
}	

void initialize(int n) {
	int i,j;
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++) g[i][j] = (i!=j);
	}
	nn = n;
}

int hasEdge(int u, int v) {
	g[u][v] = g[v][u] = 0;
	int res = chek(nn);
	if(!res){
		g[u][v] = g[v][u] = 1;
		return 1;
	}
    return 0;
}

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