Submission #283195

#	Time	Username	Problem	Language	Result	Execution time	Memory
283195		abyyskit	Game (IOI14_game)	C++14	100 / 100	740 ms	25592 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back

struct node{
	set<int> e;
};

vector<node> g;

vector<vector<int>> G;
vector<int> pos;
int U;
int V;

void initialize(int n) {
	G.resize(n, vector<int>(n));
	g.resize(n);
	srand(5);
	vector<int> start(n);
	FOR(i, 0, n){
		start[i] = i;
	}
	random_shuffle(start.begin(), start.end());
	FOR(i, 0, n - 1){
		g[start[i]].e.insert(start[i + 1]);
		g[start[i + 1]].e.insert(start[i]);
		G[start[i]][start[i + 1]] = 1;
		G[start[i + 1]][start[i]] = 1;
		G[start[i]][start[i]] = -1;
	}
	G[start[n - 1]][start[n - 1]] = -1;
}

bool dfs(int start, int par){
//	cout << "  dfs\n";
	for(auto nex: g[start].e){
		//cout << "  " << nex << "\n";
		if (nex != par){
			if (G[U][nex] == 0){
				G[U][nex] = 1;
				G[nex][U] = 1;
				g[U].e.insert(nex);
				g[nex].e.insert(U);
				g[V].e.erase(U);
				g[U].e.erase(V);
				G[U][V] = -1;
				G[V][U] = -1;
				return true;	
			}
			if(dfs(nex, start)){
				return true;
			}	
		}
	}
	return false;
}

int hasEdge(int u, int v) {
	if (G[u][v] != 1){
		G[u][v] = -1;
		G[v][u] = -1;
		return 0;
	}
	else{
		U = u;
		V = v;
		pos = {};
		if (dfs(v, u)){
			return 0;
		}
		FOR(i, 0, pos.size()){
			if (G[u][pos[i]] == 0){
				G[u][pos[i]] = 1;
				G[pos[i]][u] = 1;
				g[u].e.insert(pos[i]);
				g[pos[i]].e.insert(u);
				g[v].e.erase(u);
				g[u].e.erase(v);
				G[u][v] = -1;
				G[v][u] = -1;
				return 0;
			}
		}
		pos = {};
		swap(v, u);
		U = u;
		V = v;
		if (dfs(v, u)){
			return 0;
		}
		FOR(i, 0, pos.size()){
			if (G[u][pos[i]] == 0){
				G[u][pos[i]] = 1;
				G[pos[i]][u] = 1;
				g[u].e.insert(pos[i]);
				g[pos[i]].e.insert(u);
				g[v].e.erase(u);
				g[u].e.erase(v);
				G[u][v] = -1;
				G[v][u] = -1;
				return 0;
			}
		}
	}
	return 1;

}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   74 |   FOR(i, 0, pos.size()){
      |       ~~~~~~~~~~~~~~~~                 
game.cpp:74:3: note: in expansion of macro 'FOR'
   74 |   FOR(i, 0, pos.size()){
      |   ^~~
game.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   94 |   FOR(i, 0, pos.size()){
      |       ~~~~~~~~~~~~~~~~                 
game.cpp:94:3: note: in expansion of macro 'FOR'
   94 |   FOR(i, 0, pos.size()){
      |   ^~~

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