#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "simurgh.h"
// static int MAXQ = 30000;
// static int n, m, q = 0;
// static vector<int> u, v;
// static vector<bool> goal;
// static vector<int> parent;
// static int find(int node) {
// return (parent[node] == node ? node : parent[node] = find(parent[node]));
// }
// static bool merge(int v1, int v2) {
// v1 = find(v1);
// v2 = find(v2);
// if (v1 == v2)
// return false;
// parent[v1] = v2;
// return true;
// }
// static void wrong_answer() {
// printf("NO\n");
// exit(0);
// }
// static bool is_valid(const vector<int>& r) {
// if(int(r.size()) != n - 1)
// return false;
// for(int i = 0; i < n - 1; i++)
// if(r[i] < 0 || r[i] >= m)
// return false;
// parent.resize(n);
// for (int i = 0; i < n; i++) {
// parent[i] = i;
// }
// for (int i = 0; i < n - 1; i++) {
// if (!merge(u[r[i]], v[r[i]])) {
// return false;
// }
// }
// return true;
// }
// static int _count_common_roads_internal(const vector<int>& r) {
// if (!is_valid(r))
// wrong_answer();
// int common = 0;
// for(int i = 0; i < n - 1; i++) {
// bool is_common = goal[r[i]];
// if (is_common)
// common++;
// }
// return common;
// }
// int count_common_roads(const vector<int>& r) {
// q++;
// if(q > MAXQ)
// wrong_answer();
// return _count_common_roads_internal(r);
// }
int pp[ N ] , ss[ N ] ;
void create( int node ){
pp[ node ] = node ;
ss[ node ] = 1 ;
return ;
}
int findd( int node ){
if( pp[ node ] == node ) return node ;
return pp[ node ] = findd( pp[ node ] ) ;
}
void unite( int a , int b ){
if( ss[ a ] < ss[ b ] ) swap( a , b ) ;
if( ss[ a ] == ss[ b ] ) ss[ a ] ++ ;
pp[ b ] = a ;
return ;
}
int gd[ N ] ;
vector < int > V[ N ] ;
vector < int > rod[ N ] ;
int hs[ N ] , son[ N ] ;
int ddf( int node , int ppp ){
int tt = -1 ;
int test = 0 ;
for( auto x : V[ node ] ){
if( x == ppp ) continue ;
tt = max( tt , ddf( x , node ) ) ;
if( son[ x ] == -1 ) test = -1 ;
}
if( test == 0 && gd[ node ] == 0 ) tt = node ;
if( gd[ node ] != 1 ) test = -1 ;
son[ node ] = test ;
return tt ;
}
int titu[ N ] ;
vector<int> find_roads(int n, vector<int> u, vector<int> vv){
FOR( i , u.size() ){
rod[ u[ i ] ].pb( i ) ;
rod[ vv[ i ] ].pb( i ) ;
}
vector < int > ans ;
while( ans.size() != n - 1 ){
vector < int > cur ;
FOR( i , n ) create( i ) , V[ i ].clear() ;
for( auto x : ans ){
hs[ x ] = 1 ;
V[ u[ x ] ].pb( vv[ x ] ) ;
V[ vv[ x ] ].pb( u[ x ] ) ;
int a = u[ x ] , b = vv[ x ] ;
cur.pb( x ) ;
a = findd( a ) ;
b = findd( b ) ;
unite( a , b ) ;
}
FOR( i , n ){
if( hs[ i ] == 1 ) continue ;
int a = u[ i ] , b = vv[ i ] ;
int A = a , B = b ;
a = findd( a ) ; b = findd( b ) ;
if( a == b ) continue ;
cur.pb( i ) ;
unite( a , b ) ;
V[ A ].pb( B ) ; V[ B ].pb( A ) ;
}
int node = ddf( 0 , - 1 ) ;
int axla = count_common_roads( cur ) ;
if( axla == n - 1 ){
ans = cur ; break ;
}
for( auto x : rod[ node ] ){
titu[ x ] = 1 ;
}
FOR( i , cur.size() ){
if( titu[ cur[ i ] ] == 1 && hs[ cur[ i ] ] == 0 ){
cur.erase( cur.begin() + i ) ;
break ;
}
}
pair < int , int > mx = { -1 , -1 } ;
for( auto x : rod[ node ] ){
if( hs[ x ] == 0 && count( cur.begin() , cur.end() , x ) != false ){
cur.pb( x ) ;
int axla = count_common_roads( cur ) ;
cur.pop_back() ;
if( axla > mx.f ){
mx = { axla , x } ;
}
}
titu[ x ] = 0 ;
}
ans.pb( mx.s ) ;
gd[ node ] = 1 ;
}
sort( ans.begin() , ans.end() ) ;
return ans ;
}
// int main() {
// assert(2 == scanf("%d %d", &n, &m));
// assert(1 == scanf("%d", &MAXQ));
// u.resize(m);
// v.resize(m);
// for(int i = 0; i < m; i++)
// assert(2 == scanf("%d %d", &u[i], &v[i]));
// goal.resize(m, false);
// for(int i = 0; i < n - 1; i++) {
// int id;
// assert(1 == scanf("%d", &id));
// goal[id] = true;
// }
// vector<int> result = find_roads(n, u, v);
// if(_count_common_roads_internal(result) != n - 1)
// wrong_answer();
// printf("OK\n");
// for(int i = 0; i < (int)result.size(); i++){
// if(i)
// printf(" ");
// printf("%d", result[i]);
// }
// printf("\n");
// return 0;
// }
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
134 | FOR( i , u.size() ){
| ~~~~~~~~~~~~
simurgh.cpp:134:4: note: in expansion of macro 'FOR'
134 | FOR( i , u.size() ){
| ^~~
simurgh.cpp:139:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
139 | while( ans.size() != n - 1 ){
| ~~~~~~~~~~~^~~~~~~~
simurgh.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
170 | FOR( i , cur.size() ){
| ~~~~~~~~~~~~~~
simurgh.cpp:170:10: note: in expansion of macro 'FOR'
170 | FOR( i , cur.size() ){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9612 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9612 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9612 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
9684 KB |
correct |
| 2 |
Incorrect |
5 ms |
9684 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9612 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
