#include "simurgh.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair < int, int > pii;
vector < int > cyc, exc;
int nn, mm, p[250], d[250], cyc_len, id[250][250], gold[250][250];
bool v[250][250];
void find_cycle(){
cyc.clear();
memset( p, -1, sizeof(p) );
memset( d, -1, sizeof(d) );
queue < int > q;
q.push(0);
d[0] = 0;
int dep = 0, t1 = -1, t2, c;
while( !q.empty() ){
int sz = q.size();
dep++;
while(sz--){
int u = q.front();
// cout << u << ' ' << d[u] << ' ' << p[u] << endl;
q.pop();
for(int it = 0 ; it < nn ; it++){
if( !v[u][it] ) continue;
if( p[u] == it ) continue;
// cout << u << " --> " << *it << endl;
if( d[it] == -1 ){
p[it] = u;
d[it] = dep;
q.push(it);
}
else{
t1 = it;
t2 = u;
// cout << "Tails : " << t1 << ' ' << t2 << endl;
break;
}
}
if( t1 != -1 ) break;
}
if( t1 != -1 ) break;
}
vector < int > cw, ccw;
while( t1 != t2 ){
if( d[t1] < d[t2] ) ccw.pb(t2), t2 = p[t2];
else if( d[t1] > d[t2] ) cw.pb(t1), t1 = p[t1];
else ccw.pb(t2), cw.pb(t1), t2 = p[t2], t1 = p[t1];
}
cyc.pb(t1);
for(int i = ccw.size()-1 ; i >= 0 ; i--) cyc.pb(ccw[i]);
for(int i = 0 ; i < cw.size() ; i++) cyc.pb(cw[i]);
cyc_len = cyc.size();
cyc.pb(t1);
// cout << "Found\n";
// for(int i = 0 ; i < cyc.size() ; i++) cout << cyc[i] << ' '; cout << endl;
}
void eval(){
exc.clear();
memset(p, -1, sizeof(p));
queue < int > q;
for(int i = 0 ; i < cyc.size() ; i++) q.push(cyc[i]), p[cyc[i]] = cyc[i];
while( !q.empty() ){
int u = q.front();
q.pop();
for( int it = 0 ; it < nn ; it++ ){
if( !v[u][it] ) continue;
if( p[it] == -1 ){
p[it] = u;
// cout << "Excess : " << u << ' ' << it << endl;
exc.pb( id[u][it] );
q.push(it);
}
}
}
}
vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
memset( id, -1, sizeof(id) );
memset( gold, -1, sizeof(gold) );
nn = _n;
mm = _u.size();
for(int i = 0 ; i < mm ; i++){
v[_u[i]][_v[i]] = v[_v[i]][_u[i]] = 1;
id[_u[i]][_v[i]] = id[_v[i]][_u[i]] = i;
}
int cnt_cyc = 0;
while( mm >= nn ){
cnt_cyc++;
find_cycle();
eval();
vector < int > now;
for(int i = 0 ; i < cyc_len ; i++){
if( gold[cyc[i]][cyc[i+1]] != -1 ) {
now.pb(-1);
// cout << "Gold" << ' ' << cyc[i] << ' ' << cyc[i+1] << endl;
continue;
}
vector < int > query;
for(int j = 0 ; j < exc.size() ; j++) query.pb(exc[j]);
for(int j = 0 ; j < cyc_len ; j++){
if( i == j ) continue;
query.pb( id[cyc[j]][cyc[j+1]] );
}
now.pb( count_common_roads(query) );
// cout << "Query : "; for(int i = 0 ; i < query.size() ; i++) cout << query[i];
// cout << endl << now.back() << endl;;
}
int _mn = 1e9, _mx = -1e9;
for(int i = 0 ; i < cyc_len ; i++){
if( now[i] != -1 ) {
_mn = min( _mn, now[i] );
_mx = max( _mx, now[i] );
}
}
// cout << s.size() << endl;
if( _mn == _mx ){
for(int i = 0 ; i < cyc_len ; i++){
if( now[i] == -1 ) continue;
v[ cyc[i] ][ cyc[i+1] ] = v[ cyc[i+1] ][ cyc[i] ] = 0;
mm--;
}
continue;
}
else{
for(int i = 0 ; i < cyc_len ; i++){
if( now[i] == -1 ){
now[i] = _mn;
}
}
}
int f = -1;
for(int i = 1 ; i < cyc_len ; i++){
if( now[i] == -1 ){
f = i;
break;
}
if( now[i] != now[i-1] ){
if( now[i] < now[i-1] ) f = i;
else f = i-1;
break;
}
}
// cout << "! " << f << endl;
if( f == -1 ){
for(int i = 0 ; i < cyc_len ; i++){
v[ cyc[i] ][ cyc[i+1] ] = v[ cyc[i+1] ][ cyc[i] ] = 0;
mm--;
}
continue;
}
bool g = 1;
for(int i = f-1 ; i >= 0 ; i--){
if( now[i] != now[i+1] ) g = !g;
if( !g ){
v[ cyc[i] ][ cyc[i+1] ] = v[ cyc[i+1] ][ cyc[i] ] = 0;
mm--;
}
else{
gold[cyc[i]][cyc[i+1]] = gold[cyc[i+1]][cyc[i]] = 1;
}
}
g = 1;
for(int i = f+1 ; i < cyc_len ; i++){
if( now[i] != now[i-1] ) g = !g;
if( !g ){
v[ cyc[i] ][ cyc[i+1] ] = v[ cyc[i+1] ][ cyc[i] ] = 0;
mm--;
}
else{
gold[cyc[i]][cyc[i+1]] = gold[cyc[i+1]][cyc[i]] = 1;
}
}
}
vector < int > res;
for(int i = 0 ; i < nn ; i++){
for(int it = 0 ; it < i ; it++){
if( v[i][it] ) res.pb( id[it][i] );
}
}
// for(int i = 0 ; i < res.size() ; i++) cout << res[i] << ' ';
cout << "Cycles : " << cnt_cyc << endl;
return res;
}
/*
6 6
0 1
1 2
2 3
3 4
0 4
0 5
0 1 2 3 5
6 8
0 1
1 2
2 3
3 4
0 4
0 5
0 3
4 5
0 5 4 6 2
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/
Compilation message
simurgh.cpp: In function 'void find_cycle()':
simurgh.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < cw.size() ; i++) cyc.pb(cw[i]);
~~^~~~~~~~~~~
simurgh.cpp:20:28: warning: unused variable 'c' [-Wunused-variable]
int dep = 0, t1 = -1, t2, c;
^
simurgh.cpp: In function 'void eval()':
simurgh.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < cyc.size() ; i++) q.push(cyc[i]), p[cyc[i]] = cyc[i];
~~^~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:117:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < exc.size() ; j++) query.pb(exc[j]);
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
764 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
764 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
764 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
868 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
764 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
