Submission #1267574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267574		cmiuc	Game (IOI14_game)	C++20	15 / 100	1 ms	840 KiB

game

#include <iostream>
#include <vector>

#include "game.h"
using namespace std;
int Nn, r, dc[1505][1505], Sum[1505], k, rr;
vector<int> nei[1505];

void initialize(int N){
	Nn = N;
	r = (N * (N + 1)) / 2;
}

void update(int u){
	if (nei[u].size() != Nn - 2)
		return;
	int v = r - Sum[u] - u;
	dc[u][v] = dc[v][u] = 1;

	nei[u].push_back(v), Sum[u] += v;
	nei[v].push_back(u), Sum[v] += u;
	update(v);
}

int hasEdge(int u, int v){
	rr++;
	u++;
	v++;

	if (dc[u][v] == 1){
		k++;
		if (k == Nn - 1 and rr != r - Nn)
			cout<<1 / 0;
		return 1;
	}

	nei[u].push_back(v), Sum[u] += v;
	nei[v].push_back(u), Sum[v] += u;

	int ans = 0;
	if (nei[u].size() == Nn - 1 or nei[v].size() == Nn - 1)
		ans = 1; // check

	update(u);
	update(v);

	return ans;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:33:33: warning: division by zero [-Wdiv-by-zero]
   33 |                         cout<<1 / 0;
      |                               ~~^~~

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