제출 #1366562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1366562		enzy	게임 (IOI14_game)	C++20	100 / 100	160 ms	15952 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;


const int maxn=1510;
int qtd[maxn][maxn], pai[maxn], N;

int find(int a){
    if(pai[a]==a) return a;
    return pai[a]=find(pai[a]);
}

void merge(int a, int b){
    pai[a]=b;
    qtd[a][b]=qtd[b][a]=0;
    for(int i=0;i<N;i++) if(i!=a&&i!=b) qtd[b][i]+=qtd[a][i];
    for(int i=0;i<N;i++) if(i!=a&&i!=b) qtd[i][b]=qtd[i][a]+qtd[i][b];
}

void initialize(int n){
    N=n;
    for(int i=0;i<n;i++){
        pai[i]=i;
        for(int j=0;j<n;j++) if(i!=j) qtd[i][j]=1;
    }
}

int hasEdge(int u, int v){
    u=find(u); v=find(v);
    // cerr << "! " << u << ' ' << v << " -> " << qtd[u][v] << ' ' << qtd[v][u] << '\n';
    if(qtd[u][v]==1){
        merge(u,v);
        return 1;
    }else{
        qtd[u][v]--; 
        qtd[v][u]--;
        return 0;
    }
}

• 서브태스크 1: 15 / 15
• 서브태스크 2: 27 / 27
• 서브태스크 3: 58 / 58