제출 #757858

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757858		alexander707070	Simurgh (IOI17_simurgh)	C++14	13 / 100	119 ms	4296 KiB

simurgh

#include<bits/stdc++.h>
#include "simurgh.h"
#define MAXN 507
#define MAXM 300007
using namespace std;

int n,m,a[MAXM],b[MAXM],res[MAXM],t;
vector< pair<int,int> > vv[MAXN];
bool li[MAXN];
vector<int> tree,ask,g[MAXN],ans;
int curr,where[MAXN],maxres;
bool golden[MAXM],checked[MAXM];

void dfs(int x){
	li[x]=true;
	for(int i=0;i<vv[x].size();i++){
		if(li[vv[x][i].first])continue;

		tree.push_back(vv[x][i].second);
		dfs(vv[x][i].first);
	}
}

void comp(int x,int p,int id){
	where[x]=id;
	for(int i=0;i<g[x].size();i++){
		if(g[x][i]==p)continue;
		comp(g[x][i],x,id);
	}
}

vector<int> find_roads(int N,vector<int> from,vector<int> to){
	n=N; m=int(from.size());

	for(int i=0;i<m;i++){
		a[i]=from[i]; b[i]=to[i];

		vv[a[i]].push_back({b[i],i});
		vv[b[i]].push_back({a[i],i});
	}

	for(int i=0;i<100;i++){
		for(int f=0;f<n;f++){
			random_shuffle(vv[f].begin(),vv[f].end());
			li[f]=false;
		}
		tree.clear(); dfs(rand()%n);
		int r=rand()%tree.size();

		for(int f=0;f<n;f++)g[f].clear();
		ask.clear();

		for(int f=0;f<n-1;f++){
			if(f==r)continue;

			ask.push_back(tree[f]);
			g[a[tree[f]]].push_back(b[tree[f]]);
			g[b[tree[f]]].push_back(a[tree[f]]);
		}

		comp(a[tree[r]],-1,1);
		comp(b[tree[r]],-1,2);

		maxres=-1;
		for(int f=0;f<m;f++){
			res[f]=0;
			if(where[a[f]]!=where[b[f]]){
				ask.push_back(f);
				res[f]=count_common_roads(ask);
				maxres=max(maxres,res[f]);
				ask.pop_back();
			}
		}

		for(int f=0;f<m;f++){
			if(where[a[f]]!=where[b[f]] and res[f]==maxres){
				golden[f]=true;
			}
		}
	}

	for(int i=0;i<m;i++){
		if(golden[i]){
			ans.push_back(i);
		}
	}

	return ans;
}

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

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i=0;i<vv[x].size();i++){
      |              ~^~~~~~~~~~~~~
simurgh.cpp: In function 'void comp(int, int, int)':
simurgh.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=0;i<g[x].size();i++){
      |              ~^~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30