oj.uz

Submission #118884

# Submission time Handle Problem Language Result Execution time Memory
118884 2019-06-20T00:33:09 Z andremfq Game (IOI14_game) C++17
0 / 100
 2 ms 384 KB 
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAXN=1510;

set<int> s[MAXN];
int n,U,V,pai[MAXN],prof[MAXN],q[MAXN][MAXN];

void initialize(int n)
{
	for(int i=0;i<n;i++)
	{
		pai[i]=i;
		for(int j=i+1;j<n;j++)
			q[i][j]=1,	q[j][i]=1;
	}	
}

void see()
{
	for(int i=0;i<n;i++)
	{
		set<int> :: iterator it;
		printf("U = %d : \n",i);
		for(it=s[i].begin();it!=s[i].end();it++)
			printf("%d ",*it);
		printf("\n\n");
	}
}

int fd(int v)
{
	if(v==pai[v])	return v;
	return pai[v]=fd(pai[v]);
}

void join(int a,int b)
{
	a=fd(a);	b=fd(b);
	if(a==b)	return;
	
	if(prof[a]>prof[b])
	{	
		pai[b]=a;
		for(int i=0;i<n;i++)
			q[a][i]+=q[b][i];	
		return;
	}
	
	for(int i=0;i<n;i++)
		q[b][i]+=q[a][i];
	pai[a]=b;
	
	if(prof[a]==prof[b])	prof[b]++;
}

int hasEdge(int u,int v)
{	
	if(q[u][v]>1)
	{
		q[u][v]--;	q[v][u]--;
		return 0;
	}
	else join(u,v);
	return 1;
}
/*
int main ()
{
	scanf("%d",&n);
	
	initialize(n);
	
	for(int i=0;i<n*(n-1)/2;i++)
	{
		scanf("%d %d",&U,&V);
		
		printf("%d\n",hasEdge(U,V));
	}
}*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -