#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
#define _ int v, int tl, int tr, int l, int r, int h
#define tm (tl + tr >> 1)
#define sol v+v,tl,tm,l,r,h
#define sag v+v+1,tm+1,tr,l,r,h
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N = 1e3 + 3;
vector < int > v, dfstree;
int T[N],A[N][N],H[N],X,n;
void f(int x, int p){
H[x] = 1;
for(int y=0; y<n; y++){
if(H[y] || A[x][y] == -1) continue;
f(y,x);
dfstree.pb(A[x][y]);
}
}
void g(int x, int p){
H[x] = 1;
v.pb(x);
for(int y=0; y<n; y++){
if(y == p || A[x][y]==-1) continue;
if(H[y]){
if(A[x][y] != -1) continue;
int i,j,a,b;
for(i=0;i<v.size();i++) if(v[i] == y) break;
bool h=0,h2=0;
for(j=i;j<v.size()-1; j++){
if(T[ A[ v[j] ][ v[j+1] ] ] == 0) h=1;
if(T[ A[ v[j] ][ v[j+1] ] ] == -1) h2=1;
}
if(h==1){
for(j=i;j<v.size()-1; j++)
if(T[ A[ v[j] ][ v[j+1] ] ] == -1)
T[ A[ v[j] ][ v[j+1] ] ] = 1;
T[ A[x][y] ] = 1;
continue;
}
if(h2 == 0){
T[ A[x][y] ] = 0; continue;
}
for(j=i;j<v.size()-1; j++){
a = v[j]; b = v[j+1];
if(T[ A[a][b] ] == 1) continue;
vector < int > qry;
for(i=0;i<dfstree.size();i++) if(dfstree[i] != A[a][b]) qry.pb(dfstree[i]);
qry.pb(A[x][y]);
int com = count_common_roads(qry);
if(com == X) { T[ A[a][b] ] = 1; T[ A[x][y] ] = 1; }
if(com == X+1) { T[ A[a][b] ] = 0; T[ A[x][y] ] = 1; }
if(com == X-1) { T[ A[a][b] ] = 1; T[ A[x][y] ] = 0; }
}
}
else g(y,x);
}
v.pop_back();
}
vector<int> find_roads(int a, vector<int> u, vector<int> v) {
int i;
memset(A , -1 , sizeof A);
memset(T , -1 , sizeof T);
for(i=0;i<v.size();i++) A[ v[i] ][ u[i] ] = A[ u[i] ][ v[i] ] = i;
n = a;
memset(H , 0 , sizeof H);
f(1,0);
X = count_common_roads(dfstree);
memset(H , 0 , sizeof H);
g(1,0);
vector < int > ans;
for(i=0;i<v.size();i++)
if(T[i] != 0)
ans.pb(i);
if(ans.size() != n-1) assert(0);
return ans;
}
Compilation message
simurgh.cpp: In function 'void g(int, int)':
simurgh.cpp:40:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v.size();i++) if(v[i] == y) break;
^
simurgh.cpp:42:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=i;j<v.size()-1; j++){
^
simurgh.cpp:47:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=i;j<v.size()-1; j++)
^
simurgh.cpp:56:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=i;j<v.size()-1; j++){
^
simurgh.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<dfstree.size();i++) if(dfstree[i] != A[a][b]) qry.pb(dfstree[i]);
^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:77:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v.size();i++) A[ v[i] ][ u[i] ] = A[ u[i] ][ v[i] ] = i;
^
simurgh.cpp:85:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v.size();i++)
^
simurgh.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans.size() != n-1) assert(0);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
8312 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
8312 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
8312 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8384 KB |
correct |
| 2 |
Runtime error |
9 ms |
8504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
8312 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
