# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
70362 | Angelos | 게임 (IOI14_game) | C11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "grader.h"
//#include "game.h"
#include <bits/stdc++.h>
#define MAXN 1510
int R[MAXN] , S[MAXN][MAXN] , sz[MAXN] , dis[MAXN] , N;
using namespace std;
void initialize(int n) {
memset(dis , 0 , sizeof dis);
N = n;
for(int i=0; i<n; i++) R[i] = i , sz[i] = 1;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
S[i][j] = (i != j) ? 1 : 0;
}
int fat(int x){
if(R[x] == x) return x;
R[x] = fat(R[x]);
return R[x];
}
void unionn(int a , int b){
int A = fat(a) , B = fat(b);
if(sz[B] > sz[A]) swap(A , B);
if(sz[A] >= sz[B]) {
for(int i=0; i<N; i++)
if(i != A && i != B && !dis[i]) {S[A][i] += S[B][i];S[i][A] = S[A][i];}
sz[A] += sz[B];
dis[B] = 1;
R[B] = A;
}
}
int hasEdge(int u, int v){
int U = fat(u) , V = fat(v);
//cout << "fathers : " << U <<"->" << V << " " << S[U][V] << " " << V <<"->" << U << " " << S[V][U] << endl;
if(U == V || S[U][V] > 1) {
S[U][V] --;
S[V][U] --;
return 0;
}
unionn(u , v);
return 1;
}