Submission #292331

#	Time	Username	Problem	Language	Result	Execution time	Memory
292331		VodkaInTheJar	Game (IOI14_game)	C++14	100 / 100	531 ms	8568 KiB

game

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1503; 
const int k = 40; 

int cnt[maxn][maxn];
vector <int> adj[maxn];
int n, cnt_buckets; 
void initialize(int m)
{
	n = m;
	cnt_buckets = (n - 1) / k; 
	for (int i = 1; i <= n; i++)
	for (int j = i + 1; j <= n; j++)
	{
		if ((i - 1) / k == (j - 1) / k)
		adj[i].push_back(j), adj[j].push_back(i);
		
		else 
		cnt[(i - 1) / k][(j - 1) / k]++, cnt[(j - 1) / k][(i - 1) / k]++; 
	}
}

int cnt_used = 0; 
bool used[maxn];
void dfs1(int ver)
{
	used[ver] = true;
	cnt_used++;
	 
	for (int i = 0; i <= cnt_buckets; i++)
	if (!used[i] && cnt[ver][i])
	dfs1(i);
}

void dfs2(int ver)
{
	used[ver] = true;
	cnt_used++;
	
	for (auto i: adj[ver])
	if (!used[i])
	dfs2(i);
}

int hasEdge(int u, int v)
{
	u++;
	v++;
	
	if ((u - 1) / k == (v - 1) / k)
	{
		auto it1 = find(adj[u].begin(), adj[u].end(), v);
		auto it2 = find(adj[v].begin(), adj[v].end(), u);
		adj[u].erase(it1);
		adj[v].erase(it2);
		
		int first = (u - 1) / k * k + 1; 
		int last = min(n, first + k - 1); 
		for (int i = first; i <= last; i++)
		used[i] = false;
		
		cnt_used = 0; 
		dfs2(first);
		
		if (cnt_used != last - first + 1)
		{
			adj[u].push_back(v);
			adj[v].push_back(u);
			return 1; 
		}
		
		return 0; 
	}
	
	else 
	{
		cnt[(u - 1) / k][(v - 1) / k]--;
		cnt[(v - 1) / k][(u - 1) / k]--;
		
		if (cnt[(u - 1) / k][(v - 1) / k] >= 1)
		return 0;
		
		for (int i = 0; i <= cnt_buckets; i++)
		used[i] = false;
		
		cnt_used = 0;
		dfs1(0);
		
		if (cnt_used != cnt_buckets + 1)
		{
			cnt[(u - 1) / k][(v - 1) / k]++;
		    cnt[(v - 1) / k][(u - 1) / k]++;
		    return 1; 
		}
		
		return 0; 
	}
}

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