Submission #210699

#	Time	Username	Problem	Language	Result	Execution time	Memory
210699		peuch	Game (IOI14_game)	C++17	15 / 100	6 ms	504 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1600;

int marcAux;
int marc[MAXN], ponte[MAXN][MAXN], temp[MAXN], ingrau[MAXN];
int N, t;

vector<int> ar[MAXN];

int dfs(int cur, int pai){  
    int menor = temp[cur] = t++;
    marc[cur] = marcAux;
    int filhos = 0;
    for(int i = 0; i < ar[cur].size(); i++){
    	int viz = ar[cur][i];
       	if(marc[viz] != marcAux){
          	filhos++;
          	int m = dfs(viz, cur);
          	menor = min(menor, m);
          	if(temp[cur] < m)
              	ponte[cur][viz] = 1, ponte[viz][cur] = 1;
      	}
      	else if(viz != pai)
          	menor = min(menor, temp[viz]);
    } 
    return menor;      
}

void initialize(int n) {
	N = n;
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			ar[i].push_back(j);
			ar[j].push_back(i);
			ingrau[i]++;
			ingrau[j]++;
		}
	}
}

int hasEdge(int u, int v){
	//printf("\t%d\n", ponte[u][v]);
	if(ponte[u][v] == 1) return 1;
	else{
		int id = -1;
		for(int i = 0; i < ar[u].size(); i++)
			if(ar[u][i] == v) id = i;
		if(id < 0) return 0;
		ar[u].erase(ar[u].begin() + id);
		for(int i = 0; i < ar[v].size(); i++)
			if(ar[v][i] == u) id = i;
		if(id < 0) return 0;
		ar[v].erase(ar[v].begin() + id);
		ingrau[v]--;
		ingrau[u]--;
		if(ingrau[v] == 1 || ingrau[u] == 1){
			marcAux++;
			t = 1;
			dfs(0, -1);
		}
		return 0;
	}
}

Compilation message (stderr)

game.cpp: In function 'int dfs(int, int)':
game.cpp:17:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ar[cur].size(); i++){
                    ~~^~~~~~~~~~~~~~~~
game.cpp: In function 'int hasEdge(int, int)':
game.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ar[u].size(); i++)
                  ~~^~~~~~~~~~~~~~
game.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ar[v].size(); i++)
                  ~~^~~~~~~~~~~~~~

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