제출 #759225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
759225		Dan4Life	게임 (IOI14_game)	C++17	100 / 100	351 ms	25108 KiB

game

#include <bits/stdc++.h>
using namespace std;
int cnt[1501][1501];
int n, z, p[1501], s[1501], v[1501];

int f(int i){return i==p[i]?i:p[i]=f(p[i]);}

int unionSet(int x, int y){
    fill(v,v+n,0); z=f(0);
    if(s[x]<s[y]) swap(x,y);
    p[y]=x; s[x]+=s[y]; v[x]=v[y]=1;
    for(int i = 0; i < n; z=f(i), i++)
        if(!v[z]) cnt[z][x]+=cnt[z][y], cnt[x][z]+=cnt[y][z], v[z]=1;
    return 1;
}

void initialize(int N){
    n = N; fill(s,s+n,1); iota(p,p+n,0);
}

int hasEdge(int u, int v){
    u = f(u), v = f(v);
    cnt[u][v]++, cnt[v][u]++;
    if(cnt[u][v]!=s[u]*s[v]) return 0;
    return unionSet(u,v);
}

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