제출 #776207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776207		kingfran1907	Simurgh (IOI17_simurgh)	C++14	0 / 100	2 ms	324 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
const int maxn = 510;
vector< pair<int, int> > graph[maxn], graph2[maxn];

vector< int > v;
bool bio[maxn];
int n;
void dfs(int x) {
	bio[x] = true;
	for (auto iter : graph[x]) {
		int tren = iter.X;
		int ind = iter.Y;
		if (!bio[tren]) {
			v.push_back(ind);
			dfs(tren);
		}
	}
}

std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
	n = N;
	int m = U.size();
	for (int i = 0; i < m; i++) {
		graph[U[i]].push_back({V[i], i});
		graph[V[i]].push_back({U[i], i});
	}
	
	dfs(1);
	
	vector< int > sol;
	vector< int > c = v;
	//for (int tren : c) printf("%d ", tren); printf("\n");
	for (auto iter : c) {
		int a = U[iter];
		int b = V[iter];
		for (int i = 0; i < n; i++) bio[i] = false;
		bio[a] = bio[b] = true;
		v.clear();
		dfs(a);
		
		vector< int > qs;
		for (auto tr : c) {
			if (tr != iter) qs.push_back(tr);
		}
		bio[b] = false;
		map< int, vector<int> > ms;
		for (int i = 0; i < m; i++) {
			int x = U[i];
			int y = V[i];
			if ((int)bio[x] + bio[y] == 1) {
				qs.push_back(i);
				//for (int tren : qs) printf("%d ", tren); printf("\n");
				int out = count_common_roads(qs);
				//printf("number: %d\n", out);
				ms[out].push_back(i);
				qs.pop_back();
			}
		}
		if (ms.size() == 2) ms.erase(ms.begin());
		for (int tren : ms.begin()->Y) sol.push_back(tren);
	}
	//printf("out: ");
	//for (int tren : sol) printf("%d ", tren); printf("\n");
	sort(sol.begin(), sol.end());
	sol.resize(unique(sol.begin(), sol.end()) - sol.begin());
	return sol;
}

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