Submission #294798

#	Time	Username	Problem	Language	Result	Execution time	Memory
294798		mieszko11b	Game (IOI14_game)	C++14	42 / 100	9 ms	640 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

int n;
bool known[107][107];
int G[107][107];
vector<int> in[107];
int scc[107];

void initialize(int n) {
	::n = n;
	memset(known, 0, sizeof known);
	memset(G, 0, sizeof G);
	for(int i = 0 ; i < n ; i++) {
		scc[i] = i;
		in[i].clear();
		in[i].push_back(i);
	}
}

void set_edge(int u, int v, int s) {
	known[u][v] = known[v][u] = 1;
	G[u][v] = G[v][u] = s;
}

int hasEdge(int u, int v) {
    if(known[u][v])
		return G[u][v];
	if(scc[u] == scc[v]) {
		set_edge(u, v, 1);
		return 1;
	}
	
	int cnt = 0;
	for(int x : in[scc[u]])
		for(int y : in[scc[v]])
			if(known[x][y])
				cnt++;
				
	int all = in[scc[u]].size() * in[scc[v]].size();
	
	//~ cout << u << " " << v << " " << all << " " << cnt << endl;
	
	if(cnt + 1 == all) {
		set_edge(u, v, 1);
		int s = scc[v];
		for(int x : in[s]) {
			in[scc[u]].push_back(x);
			scc[x] = scc[u];
		}
		in[s].clear();
		return 1;
	}
	
	set_edge(u, v, 0);
	return 0;
}

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