Submission #70323

#	Time	Username	Problem	Language	Result	Execution time	Memory
70323		E869120	Simurgh (IOI17_simurgh)	C++14	13 / 100	698 ms	45144 KiB

simurgh

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

vector<vector<pair<int,int> > >vec; int N, p[7][7];

void dfs(vector<pair<int,int> > v) {
	if((int)v.size() == N - 1) {
		sort(v.begin(), v.end());
		vec.push_back(v);
		return;
	}
	bool used[7] = {0, 0, 0, 0, 0, 0, 0};
	for (int i = 0; i < (int)v.size(); i++) { used[v[i].first] = true; used[v[i].second] = true; }
	
	if (v.size() == 0) used[0] = true;
	
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (p[i][j] == 0 || used[i] == used[j]) continue;
			vector<pair<int,int>> Z = v;
			Z.push_back(make_pair(i, j));
			dfs(Z);
		}
	}
}

void init() {
	dfs(vector<pair<int,int>>{});
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N = n; for (int i = 0; i < (int)u.size(); i++) { p[u[i]][v[i]] = i + 1; p[v[i]][u[i]] = i + 1; }
	init();
	
	for (int i = 0; i < (int)vec.size(); i++){
		vector<int> T;
		for (int j = 0; j < (int)vec[i].size(); j++) T.push_back(p[vec[i][j].first][vec[i][j].second] - 1);
		sort(T.begin(), T.end());
		
		int val = count_common_roads(T);
		if (val == N - 1) return T;
	}
	return vector<int>{ -1 };
}

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