Submission #135909

#	Time	Username	Problem	Language	Result	Execution time	Memory
135909		vince	Game (IOI14_game)	C++14	100 / 100	533 ms	25436 KiB

game

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <queue>
#include <set>
#include <stack>

using namespace std;

#define long long long
#define fi first
#define se second
typedef pair<int,int> ii;

int n;
int parent[1503];
int A[1503][1503];
vector<int> mem[1503];

void print()
{
	// for(int i = 0; i < n; i++)
	// {
	// 	printf("	");
	// 	for(int j = 0; j < n; j++)
	// 		printf("%d ", A[i][j]);
	// 	printf("\n");
	// }
	// printf("\n");
}

void initialize(int N)
{
	n = N;
	for(int i = 0; i < n; i++) mem[i] = {i}, parent[i] = i;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(i != j)
				A[i][j] = 1;

	print();
}

int hasEdge(int u, int v) 
{
	// printf("%d %d %d %d\n", u, v, parent[u], parent[v]);
	u = parent[u]; v = parent[v];
	if(A[u][v] == 1)
	{
		for(int i = 0; i < n; i++)
		{
			A[u][i] += A[v][i];
			A[i][u] += A[i][v];
			A[v][i] = A[i][v] = 0;
		}
		A[u][u] = 0;
		for(int x : mem[v])
		{
			mem[u].push_back(x);
			parent[x] = u;
			// printf("	X : %d %d\n", x, parent[x]);
		}
		// print();
		return 1;
	}
    else
    {
    	A[u][v]--;
    	A[v][u]--;
    	// print();
    	return 0;
    }
}

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