# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
70362 | Angelos | Game (IOI14_game) | C11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}