oj.uz

Submission #776207

# Submission time Handle Problem Language Result Execution time Memory
776207 2023-07-07T12:33:05 Z kingfran1907 Simurgh (IOI17_simurgh) C++14
0 / 100
 2 ms 324 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB correct
2 Incorrect 1 ms 212 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB WA in grader: NO
2 Halted 0 ms 0 KB -