Submission #283182

#	Time	Username	Problem	Language	Result	Execution time	Memory
283182		abyyskit	Game (IOI14_game)	C++14	0 / 100	1 ms	384 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;

void initialize(int n) {
	G.resize(n, vector<int>(n));
	g.resize(n);
	srand(5);
	vector<int> start(n);
	FOR(i, 0, n - 1){
		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;
}

void dfs(int start, int par){
//	cout << "  dfs\n";
	for(auto nex: g[start].e){
		//cout << "  " << nex << "\n";
		if (nex != par){
			pos.pb(nex);
			dfs(nex, start);	
		}
	}
}

int hasEdge(int u, int v) {
	if (G[u][v] != 1){
		G[u][v] = -1;
		G[v][u] = -1;
		return 0;
	}
	else{
		pos = {};
		dfs(v, u);
		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);
		dfs(v, u);
		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)
......
   55 |   FOR(i, 0, pos.size()){
      |       ~~~~~~~~~~~~~~~~                 
game.cpp:55:3: note: in expansion of macro 'FOR'
   55 |   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)
......
   71 |   FOR(i, 0, pos.size()){
      |       ~~~~~~~~~~~~~~~~                 
game.cpp:71:3: note: in expansion of macro 'FOR'
   71 |   FOR(i, 0, pos.size()){
      |   ^~~

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