제출 #1060610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1060610		vjudge1	게임 (IOI14_game)	C++17	100 / 100	218 ms	32688 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int INF=100000000;


int father[2000];
int cnt[2000][2000];
int tamano[2000];
int N;

void findF(int x, int y){
    for(int i=0;i<N;i++){
        if(father[i]==x){
            father[i]=y;
        }
    }

}

void initialize(int n) {
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<n;i++){
        father[i]=i;
        tamano[i]=1;
    }
    N=n;
}

void calcu(int x, int y){
    for(int i=0;i<N;i++){
        cnt[y][i]+=cnt[x][i];
        cnt[i][y]+=cnt[i][x];
    }
}

int hasEdge(int u, int v) {
    u=father[u];
    v=father[v];
    if(v>u)swap(u,v);
    cnt[u][v]++;
    cnt[v][u]++;
    //cout<<father[u]<<" "<<father[v]<<" FATHER"<<endl;
    //cout<<tamano[u]<<" "<<tamano[v]<<" TAMANO"<<endl;
    //cout<<cnt[u][v]<<" CNT"<<endl;

    if(tamano[u]*tamano[v]==cnt[u][v]){
        //if(tamano[v]>tamano[u])swap(u,v);

        findF(v,u);
        calcu(v,u);
        tamano[u]+=tamano[v];
        return 1;
    }else{
        return 0;
    }

}

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