Submission #423162

#	Time	Username	Problem	Language	Result	Execution time	Memory
423162		Pbezz	Simurgh (IOI17_simurgh)	C++14	13 / 100	24 ms	296 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN=2e5+5;
const ll INF=1e9+7;

bitset<10>visited;
vector<vector<ll>>adj(10);
bool ok=true;

void dfs(ll node, ll p){ if(ok==false)return;
visited[node]=1;

for(auto next:adj[node]){if(ok==false)return;
if(next==p)continue;

if(visited[next]==1){
ok=false; return;
}

dfs(next,node);

}

}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	std::vector<int> r(n - 1);

	ll m=(ll)u.size(),i,k;

	for(i=0;i<(1LL<<m);i++){

	if(__builtin_popcountll(i)!=n-1)continue;

//	cout<<i<<endl;

	visited.reset();

	for(k=0;k<n;k++)adj[k].resize(0);

	for(k=0;k<m;k++){
	if(i&(1LL<<k)){
	adj[u[k]].pb(v[k]);
	adj[v[k]].pb(u[k]);
	
	}
}
	ok=true;
	dfs(0,-1);

	if(ok==false)continue;

	if((ll)visited.count()==n){
	r.resize(0);

	for(k=0;k<m;k++){
	if(i&(1LL<<k)){
	r.pb(k);
	}
	}

	if(count_common_roads(r)==n-1)return r;

}

}




	return r;
}

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