제출 #70364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70364		Angelos	게임 (IOI14_game)	C++11	100 / 100	810 ms	27584 KiB

game

//#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;
}

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