제출 #127319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
127319		nxteru	게임 (IOI14_game)	C++14	42 / 100	1071 ms	30328 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct UF{
	int n,par[1505],rs[1505],sz[1505];
	void ini(int x,int v){
		n=x;
		for(int i=0;i<n;i++){
			par[i]=i;
			if(i==v)rs[i]=0;
			else rs[i]=1;
			sz[i]=1;
		}
	}
	int find(int x){
		if(par[x]==x)return x;
		return par[x]=find(par[x]);
	}
	void unit(int v,int u){
		v=find(v);
		u=find(u);
		if(sz[v]<sz[u])swap(u,v);
		rs[v]+=rs[u];
		par[u]=v;
		sz[v]+=sz[u];
	}
};
int n,par[1505],sz[1505];
UF p[1505];
int find(int x){
	if(par[x]==x)return x;
	return par[x]=find(par[x]);
}
void unit(int v,int u){
	v=find(v);
	u=find(u);
	if(sz[v]<sz[u])swap(u,v);
	for(int i=0;i<n;i++)p[v].rs[i]+=p[u].rs[i];
	par[u]=v;
	sz[v]+=sz[u];
}
void initialize(int N) {
	n=N;
	for(int i=0;i<n;i++)par[i]=i,p[i].ini(n,i),sz[i]=1;
}

int hasEdge(int u, int v) {
    u=find(u);
    v=find(v);
    if(u==v)return 1;
    p[u].rs[v]--;
	p[v].rs[u]--;
    if(p[u].rs[v]>0)return 0;
	else{
		for(int i=0;i<n;i++)p[i].unit(v,u);
		unit(v,u);
		return 1;
	}
}

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