Submission #294824

#	Time	Username	Problem	Language	Result	Execution time	Memory
294824		mieszko11b	Game (IOI14_game)	C++14	100 / 100	705 ms	36792 KiB

game

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

using namespace std;

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

void initialize(int n) {
	::n = n;
	memset(known, 0, sizeof known);
	memset(G, 0, sizeof G);
	memset(cnt, 0, sizeof cnt);
	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 all = in[scc[u]].size() * in[scc[v]].size();
	
	//~ cout << u << " " << v << " " << all << " " << cnt << endl;
	
	if(cnt[scc[u]][scc[v]] + 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();
		
		for(int i = 0 ; i < n ; i++) {
			int su = cnt[scc[u]][i] + cnt[s][i];
			cnt[scc[u]][i] = cnt[i][scc[u]] = su;
		}
		
		return 1;
	}
	
	set_edge(u, v, 0);
	cnt[scc[u]][scc[v]]++;
	cnt[scc[v]][scc[u]]++;
	return 0;
}

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