제출 #236310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236310		crossing0ver	게임 (IOI14_game)	C++17	100 / 100	485 ms	17016 KiB

game

#include<bits/stdc++.h>
#include "game.h"
using namespace std;
 
int A[1500][1500],sz[1500],P[1500];
int par (int a) {
	return a == P[a] ? a : P[a] = par (P[a]);
}
 
int join(int a,int b) {
	int x = par(a);
	int y = par(b);
	if (x == y) return 0;
	if (A[x][y] != 1) { A[x][y]--;A[y][x]--;return 0;}
	if (sz[x] < sz[y]) swap(x,y);
	for (int i = 0; i < 1500; i++)
		if (i != x && i != y) {
			int t = A[x][i] + A[y][i];
		A[x][i] = A[i][x] = t;
	}
	P[y] = x;
	sz[x] += sz[y];
	return 1;
}
void initialize(int n) {
  for (int i = 0; i < n; i++) {
  	sz[i] = 1;
	   P[i] = i;
	  for (int j = 0;j < n; j++) {
	  	if (i != j) A[i][j] = 1;
	  } 
  }
}
 
int hasEdge(int u, int v) {
    return join(u,v);
}

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