#include <cstdio>
#include <iostream>
#include <cassert>
#include <vector>
#include <cstdlib>
#include <string>
using namespace std;
static int MAXQ = 30000;
static int n, m, q = 0;
static vector<int> u, v;
static vector<bool> goal;
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v);
int count_common_roads(const std::vector<int>& r);
bool isSubtask1(int n) {return n<=7;}
bool isSubtask2(int n) {return n<=50;}
bool isSubtask3(int n) {return n<=240;}
bool hasBackEdge(int parent, int now, std::vector<int>& visit, std::vector<vector<int>>& edgeL) {
for(int elem: edgeL[now]) {
if (elem==parent) continue;
if (visit[elem] || hasBackEdge(now,elem,visit,edgeL)) return true;
}
return false;
}
bool isTree(std::vector<int>& edges, std::vector<int>& u, std::vector<int>& v) {
n = edges.size()+1;
std::vector<vector<int>> edgeL(n);
std::vector<int> connect(n,0);
for(int i=0; i<n-1; i++) {
int idx = edges[i];
edgeL[u[idx]].push_back(v[idx]);
edgeL[v[idx]].push_back(u[idx]);
connect[u[idx]] = connect[v[idx]] = 1;
}
cout << "edge List\n";
for(int i=0; i<n; i++) {
printf("%d: ", i);
for(int elem: edgeL[i]) printf("%d ",elem); cout << endl;
}
for(int i=0; i<n; i++) if(connect[i]==0) return false;
vector<int> visit(n,0); visit[0] = 1;
int parent = 0, now = 0;
if (!hasBackEdge(parent,now,visit,edgeL)) return true;
else return false;
}
bool selectEdges(int cnt, int start, int n, int m, std::vector<int>& edges, std::vector<int>& u, std::vector<int>& v){
if (cnt == n-1 && isTree(edges,u,v) && count_common_roads(edges)==n-1) return true;
for(int i=start; i<m; i++){
edges[cnt] = i;
if (selectEdges(cnt+1,i+1,n,m,edges,u,v)) return true;
}
return false;
}
std::vector<int> subtask1(int n, std::vector<int>& u, std::vector<int>& v) {
int m = u.size();
std::vector<int> r(n-1);
if(selectEdges(0,0,n,m,r,u,v)) return r;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
// if (isSubtask1(n))
return subtask1(n,u,v);
std::vector<int> r(n - 1);
for(int i = 0; i < n - 1; i++)
r[i] = i;
int common = count_common_roads(r);
if(common == n - 1)
return r;
r[0] = n - 1;
return r;
}
Compilation message
simurgh.cpp: In function 'bool isTree(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
simurgh.cpp:45:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
45 | for(int elem: edgeL[i]) printf("%d ",elem); cout << endl;
| ^~~
simurgh.cpp:45:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
45 | for(int elem: edgeL[i]) printf("%d ",elem); cout << endl;
| ^~~~
simurgh.cpp: In function 'std::vector<int> subtask1(int, std::vector<int>&, std::vector<int>&)':
simurgh.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
68 | }
| ^
simurgh.cpp: At global scope:
simurgh.cpp:12:18: warning: 'q' defined but not used [-Wunused-variable]
12 | static int n, m, q = 0;
| ^
simurgh.cpp:12:15: warning: 'm' defined but not used [-Wunused-variable]
12 | static int n, m, q = 0;
| ^
simurgh.cpp:10:12: warning: 'MAXQ' defined but not used [-Wunused-variable]
10 | static int MAXQ = 30000;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
