# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1061551 | fv3 | Simurgh (IOI17_simurgh) | C++14 | 9 ms | 440 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<vector<pair<int, int>>> adj;
vector<int> U, V;
vector<int> res;
void check_tree(vector<int> edges, set<int> nodes)
{
if (nodes.size() == N)
{
int common = count_common_roads(edges);
if (common == N - 1)
res = edges;
return;
}
for (auto node : nodes)
{
for (auto edge : adj[node])
{
if (nodes.count(edge.first))
continue;
nodes.insert(edge.first);
edges.push_back(edge.second);
check_tree(edges, nodes);
nodes.erase(edge.first);
edges.pop_back();
}
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
N = n; M = u.size();;
u = U; v = V;
adj = vector<vector<pair<int, int>>>(N);
for (int i = 0; i < M; i++)
{
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
check_tree({}, {0});
return res;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |