Submission #283177

#	Time	Username	Problem	Language	Result	Execution time	Memory
283177		abyyskit	Game (IOI14_game)	C++14	42 / 100	1085 ms	3396 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);
	FOR(i, 0, n - 1){
		g[i].e.insert(i + 1);
		g[i + 1].e.insert(i);
		G[i][i + 1] = 1;
		G[i + 1][i] = 1;
		G[i][i] = -1;
	}
	G[n - 1][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)
......
   49 |   FOR(i, 0, pos.size()){
      |       ~~~~~~~~~~~~~~~~                 
game.cpp:49:3: note: in expansion of macro 'FOR'
   49 |   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)
......
   65 |   FOR(i, 0, pos.size()){
      |       ~~~~~~~~~~~~~~~~                 
game.cpp:65:3: note: in expansion of macro 'FOR'
   65 |   FOR(i, 0, pos.size()){
      |   ^~~

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