Submission #399858

#	Time	Username	Problem	Language	Result	Execution time	Memory
399858		mshandilya	Game (IOI14_game)	C++14	100 / 100	467 ms	25540 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

//declaring required data objects
int nodes;
std::vector<int> node_set;
std::vector<std::list <int>> set_nodes;
std::list<int> present_sets;
std::vector<std::vector<int>> possible_connections;

void initialize(int n) {
	nodes = n;
	set_nodes.resize(n);
	possible_connections.assign(n, std::vector<int> (n, 1));
	for(int i = 0; i<n; i++) {
		node_set.push_back(i);
		set_nodes[i].push_back(i);
		present_sets.push_back(i);
		possible_connections[i][i] = 0;
	}
}

int hasEdge(int u, int v) {
	if(possible_connections[node_set[u]][node_set[v]] > 1) {
		possible_connections[node_set[u]][node_set[v]]--;
		possible_connections[node_set[v]][node_set[u]]--;
		return 0;
	}
	else if(possible_connections[node_set[u]][node_set[v]] == 0)
		return 0;
	else {
		//union of node_set[u] and node_set[v]
		int set1, set2;
		if(set_nodes[node_set[u]].size()>set_nodes[node_set[v]].size()) {
			set1 = node_set[u];
			set2 = node_set[v];
		}
		else {
			set1 = node_set[v];
			set2 = node_set[u];
		}
		for(auto& departing_node : set_nodes[set2]) {
			node_set[departing_node] = set1;
			set_nodes[set1].push_back(departing_node);
		}
		std::list<int>::iterator to_delete;
		for(std::list<int>::iterator i = present_sets.begin(); i!=present_sets.end(); i++) {
			if(*i==set2)
				to_delete = i;
			else if(*i!=set1) {
				possible_connections[set1][*i] += possible_connections[set2][*i];
				possible_connections[*i][set1] += possible_connections[*i][set2];
			}
		}
		present_sets.erase(to_delete);
		possible_connections[set1][set2] = 0;
		return 1;
	}
}

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