제출 #162995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
162995		nickmet2004	게임 (IOI14_game)	C++11	100 / 100	526 ms	25368 KiB

game

#include<bits/stdc++.h>
//#include<game.h>

using namespace std;

const int NAX = 1505;

int N;
int P[NAX] , sz[NAX];
int used[NAX][NAX];

void make_set(){
    for(int i = 0; i < N; ++i){
        P[i] = i;
        sz[i] = 1;
    }
}
int Find(int x){
    return (P[x] == x) ? x : P[x] = Find(P[x]);
}
int Union(int u , int v){
    int U = Find(u);
    int V = Find(v);
    int edges = sz[U] * sz[V];
    int x = (sz[U] >= sz[V]) ? U : V;
    int y = (sz[U] < sz[V]) ? U : V;
    ++used[x][y];
    ++used[y][x];
    if(edges == used[x][y]){
        sz[x] += sz[y];
        P[y] = x;
        for(int i = 0; i < N; ++i){
            used[x][i] += used[y][i];
            used[i][x] += used[i][y];
        }
        return 1;
    }
    return 0;
}

void initialize(int n){
    N = n;
    make_set();
}
int hasEdge(int u , int v){
    return Union(u , v);
}

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