Submission #358664

#	Time	Username	Problem	Language	Result	Execution time	Memory
358664		tengiz05	Simurgh (IOI17_simurgh)	C++17	0 / 100	4 ms	492 KiB

simurgh

#include "simurgh.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
vector<pii> edge;
vector<pii> edges[505];
int n, m;
vector<int> ans;
vector<int> now;
bool used[505];
bool found = false;
void dfs(int u){
	if(found)return;
	if((int)now.size() == n-1){
		for(int i=0;i<n;i++){
			if(!used[i] && i != u)return;
		}int t = count_common_roads(now);
		if(t == n-1){
			ans = now;
			found = true;
		}return;
	}
	used[u] = true;
	for(auto [v, id] : edges[u]){
		if(found)return;
		if(used[v])continue;
		now.pb(id);
		dfs(v);
		now.pop_back();
	}
	used[u] = false;
}
vector<int> find_roads(int Ni, vector<int> u, vector<int> v){
	n = Ni, m = u.size();
	for(int i=0;i<m;i++){
		edges[u[i]].pb({v[i],i});
		edges[v[i]].pb({u[i],i});
		edge.pb({u[i],v[i]});
	}
	for(int i=0;i<n;i++){
		memset(used,0,sizeof used);
		now.clear();
		dfs(i);
	}
	assert(found);
	return ans;
}

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