제출 #413386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413386		Antekb	게임 (IOI14_game)	C++14	42 / 100	1089 ms	3992 KiB

game

#include "game.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=1505;
unordered_set<int> E[N];
int E2[N][N];
int n;

int d[N];
vector<pair<int, int> > span;
bool bfs(int s){
	vector<int> V={s};
	d[s]=1;
	vector<pair<int, int> > span2;
	for(int i=0; i<V.size(); i++){
		//cout<<V[i]<<"a\n";
		int v=V[i];
		for(int u=0; u<n; u++){
			if(E2[v][u] && !d[u]){
				d[u]=d[v]+1;
				V.push_back(u);
				span2.push_back({min(u, v), max(u, v)});
			}
		}
	}
	for(int i:V)d[i]=0;
	if(V.size()==n)span=span2;
	return (V.size()==n);
}
int lo[N], pre[N], par[N];
int wsk;
void dfs(int v){
	pre[v]=wsk++;
	for(int u=0; u<n; u++){
		if(E2[v][u] && !pre[u]){
			par[u]=v;
			dfs(u);
			//lo[v]=min(lo[v], lo[u]);
		}
		//else if(u!=par[v])lo[v]=min(lo[v], pre[u]);
	}
}
bool check(int s){
	/*wsk=1;
	dfs(s);
	for(int u=0; u<n; u++)pre[u]=0;
	if(wsk!=n+1)return 0;
	span.clear();
	for(int u=0; u<n; u++)if(u!=s)span.push_back({min(u,par[u]), max(u, par[u])});
	return 1;*/
	return bfs(s);
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
void initialize(int _n){
	n=_n;
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			E2[i][j]=1;
			E2[j][i]=1;
		}
	}
	check(rng()%n);
}

int hasEdge(int u, int v) {
	if(u>v)swap(u, v);
   	E2[u][v]=0;
   	E2[v][u]=0;
    bool b=0;
    //cout<<u<<" "<<v<<"\n";
    for(auto j:span)if(j.st==u && j.nd==v)b=1;
    //for(auto j:span)cout<<j.st<<" "<<j.nd<<"\n";
	//cout<<"\n";
    if(!b)return 0;
    //if(E[u].size()>E[v].size())swap(u, v);
    if(check(rng()%n)){
    	return 0;
    }
    E2[u][v]=1;
    E2[v][u]=1;
    //E[u].insert(v);
    //E[v].insert(u);
    return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'bool bfs(int)':
game.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
game.cpp:29:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  if(V.size()==n)span=span2;
      |     ~~~~~~~~^~~
game.cpp:30:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  return (V.size()==n);
      |          ~~~~~~~~^~~

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