#include <bits/stdc++.h>
#include "simurgh.h"
#define debug
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int MAXN = 510 ;
const int MAXM = 510*510 ;
using namespace std ;
struct Edge
{
int j , id ;
Edge(int j = 0 , int id = 0 )
: j(j) , id(id) {}
} ;
vector<Edge> adj[MAXN] ;
vector<int> tree ;
bool marc[MAXN] , royal[MAXM] ;
int ini[MAXN] , fim[MAXN] ;
int Time ;
pii edge[MAXM] ;
// ---------------------------------
bool isInside(int x , int y)
{
return ( ini[x] > ini[y] && fim[x] <= fim[y] ) ;
}
void findRandomTree(int x)
{
marc[x] = true ;
ini[x] = ++Time ;
for(Edge e : adj[x])
if(!marc[e.j])
{
tree.pb(e.id) ;
findRandomTree(e.j) ;
}
fim[x] = Time ;
}
vector<int> find_roads(int n , vector<int> u , vector<int> v )
{
int m = u.size() ;
vector<int> ans ;
lp(i,0,m)
{
int a = u[i] , b = v[i] ;
adj[a].pb(Edge(b,i)) ;
adj[b].pb(Edge(a,i)) ;
edge[i] = mk(a,b) ;
}
//Generating a random tree
findRandomTree(0) ;
for(int i : tree) debug("%d " , i ) ;
debug("\n") ;
lp(i,0,n) debug("%d %d\n" , ini[i] , fim[i]) ;
//Sort the edges by child and parent
//The first is the 'child' or candidate to it
lp(i,0,m)
if( ini[ edge[i].ff ] < ini[ edge[i].ss ] )
swap( edge[i].ff , edge[i].ss ) ;
int num = count_common_roads(tree);
//Trying to replace each edge
for(int i = 0 ; i < n-1 ; i++ )
{
bool imRoyal = true ;
int cur = tree[i] ;
int bigChild = edge[cur].ff ;
vector<int> equalToMe ;
equalToMe.pb(cur) ;
lp(j,0,m)
{
//The 'child' must be inside bigChild subtree
//The parent mustn't
if( !isInside( edge[j].ff , bigChild ) || isInside( edge[j].ss , bigChild ) )
continue ;
tree[i] = j ;
int newNum = count_common_roads(tree) ;
tree[i] = cur ;
if(newNum == num) equalToMe.pb(j) ;
else if(newNum > num)
{
royal[j] = true ;
imRoyal = false ;
}
}
if(imRoyal)
for(int j : equalToMe)
royal[j] = true ;
}
lp(i,0,m)
if( royal[i] )
ans.pb(i) ;
return ans ;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:87:34: warning: left operand of comma operator has no effect [-Wunused-value]
for(int i : tree) debug("%d " , i ) ;
^
simurgh.cpp:88:14: warning: statement has no effect [-Wunused-value]
debug("\n") ;
^
simurgh.cpp:89:35: warning: left operand of comma operator has no effect [-Wunused-value]
lp(i,0,n) debug("%d %d\n" , ini[i] , fim[i]) ;
^
simurgh.cpp:89:35: warning: right operand of comma operator has no effect [-Wunused-value]
lp(i,0,n) debug("%d %d\n" , ini[i] , fim[i]) ;
~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
correct |
| 2 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
