#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(T[ A[x][y] ] != -1) continue;
int i;
for(i=0;i<v.size();i++) if(v[i] == y) break;
// if(i == v.size()) assert(0);
int h=0,h2=0;
for(int j=i;j<v.size()-1; j++){
if(T[ A[ v[j] ][ v[j+1] ] ] == 0) h++;
if(T[ A[ v[j] ][ v[j+1] ] ] == -1) h2=1;
}
// if(h > 1) assert(0);
if(h==1){
for(int 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(int j=i;j<v.size()-1; j++){
int a,b;
a = v[j]; b = v[j+1];
if(T[ A[a][b] ] == 1) continue;
vector < int > qry;
for(int k=0;k<dfstree.size();k++) if(dfstree[k] != A[a][b]) qry.pb(dfstree[k]);
qry.pb(A[x][y]);
// if(qry.size() != n-1) assert(0);
int com = count_common_roads(qry);
if(com == X) { T[ A[a][b] ] = 1; if(T[ A[x][y] ]==0) assert(0); T[ A[x][y] ] = 1; }
if(com == X+1) { T[ A[a][b] ] = 0; if(T[ A[x][y] ]==0) assert(0); T[ A[x][y] ] = 1; }
if(com == X-1) { T[ A[a][b] ] = 1; if(T[ A[x][y] ]==1) assert(0); 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(0,-1);
// if(dfstree.size() != n-1) assert(0);
X = count_common_roads(dfstree);
memset(H , 0 , sizeof H);
g(0,-1);
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:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=i;j<v.size()-1; j++){
^
simurgh.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=i;j<v.size()-1; j++)
^
simurgh.cpp:58:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=i;j<v.size()-1; j++){
^
simurgh.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<dfstree.size();k++) if(dfstree[k] != A[a][b]) qry.pb(dfstree[k]);
^
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:81: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:90:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v.size();i++)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4216 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4216 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4216 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4320 KB |
correct |
| 2 |
Incorrect |
4 ms |
4504 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4216 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
