MnZn WA on #24 求助
  • 板块CF19E Fairy
  • 楼主Yc_cY
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/25 20:04
  • 上次更新2023/11/3 01:13:45
查看原帖
MnZn WA on #24 求助
157953
Yc_cY楼主2023/8/25 20:04

code:

#include<bits/stdc++.h>
#define ll long long
#define INF 1e17
#define For( i , a , b ) for( register ll i = ( a ) ; i <= ( b ) ; ++i )
#define Rep( i , a , b ) for( register ll i = ( a ) ; i >= ( b ) ; --i )
using namespace std ;
inline ll read() {
    ll s = 0 ; char ch = getchar() ; bool f = 0 ;
    for( ; !isdigit( ch ) ; ch = getchar() ) f ^= !( 45 ^ ch ) ;
    for( ; isdigit( ch ) ; ch = getchar() ) s = ( s << 3 ) + ( s << 1 ) + ( ch ^ 48 ) ;
    if( f ) return -s ; return s ;
}
int ln , n , m , a[ 10005 ] , b[ 10005 ] , c[ 2 ][ 10005 ] , d[ 2 ][ 10005 ] , cnt[ 2 ];
struct edge{
    int To , Nxt , id ;
} e[ 20005 ] ;
int head[ 10005 ] , tot , dep[ 10005 ] , fa[ 25 ][ 10005 ] , bel[ 10005 ] ;
bool vis[ 10005 ] ;
void add( int u, int v , int w ) {
    e[ ++tot ].Nxt = head[ u ] ;
    e[ tot ].To = v ;
    e[ tot ].id = w ;
    head[ u ] = tot ;
}
void dfs( int x ) {
    bel[ x ] = bel[ 0 ] ;
    vis[ x ] = 1 ;
    for( int i = head[ x ] ; i ; i = e[ i ].Nxt ) {
        int v = e[ i ].To ;
        if( v == fa[ 0 ][ x ] || vis[ v ] ) continue ;
        dep[ v ] = dep[ x ] + 1 ;
        fa[ 0 ][ v ] = x ;
        dfs( v ) ;
    }
}
void getfa() {
    For( i , 1 , ln )
        For( j , 1 , n )
            fa[ i ][ j ] = fa[ i - 1 ][ fa[ i - 1 ][ j ] ] ;
}
int lca( int x , int y ) {
    if( dep[ x ] <= dep[ y ] ) swap( x , y ) ;
    Rep( i , ln , 0 ) if( fa[ i ][ x ] && dep[ fa[ i ][ x ] ] >= dep[ y ] ) x = fa[ i ][ x ] ;
    if( x == y ) return x ;
    Rep( i , ln , 0 ) if( fa[ i ][ x ] && fa[ i ][ y ] && fa[ i ][ x ] != fa[ i ][ y ] ) x = fa[ i ][ x ] , y = fa[ i ][ y ]  ;
    return fa[ 0 ][ x ] ;
}
void solve() {
  //  For( i , 1 , n ) cout << fa[ 0 ][ i ] << " " ; puts("") ;
    For( i , 1 , m ) {
        if( fa[ 0 ][ a[ i ] ] != b[ i ] && fa[ 0 ][ b[ i ] ] != a[ i ] ) {
            int tmp = lca( a[ i ] , b[ i ] ) , len = dep[ a[ i ] ] + dep[ b[ i ] ] - dep[ tmp ] - dep[ tmp ] + 1 ;
            len = len % 2 ;
            cnt[ len ] ++ ;
            c[ len ][ i ] ++ ;
            d[ len ][ a[ i ] ] ++ ;
            d[ len ][ b[ i ] ] ++ ;
            d[ len ][ tmp ] -- ;
            d[ len ][ fa[ 0 ][ tmp ] ] -- ;
        }
    }
    memset( vis , 0 , sizeof vis ) ;
}
void dfs2( int x , int num ) {
    vis[ x ] = 1 ;
    for( int i = head[ x ] ; i ; i = e[ i ].Nxt ) {
        int v = e[ i ].To ;
        if( v == fa[ 0 ][ x ] || vis[ v ] ) continue ;
        dfs2( v , e[ i ].id ) ;
    //    cout << x << " " << v << endl ;
        d[ 0 ][ x ] += d[ 0 ][ v ] ;
        d[ 1 ][ x ] += d[ 1 ][ v ] ;
    }
    c[ 0 ][ num ] += d[ 0 ][ x ] ;
    c[ 1 ][ num ] += d[ 1 ][ x ] ;
}
int main() {
    n = read() ;
    m = read() ;
    ln = log2( n ) + 1 ;
    For( i , 1 , m )
        a[ i ] = read() , b[ i ] = read() , add( a[ i ] , b[ i ] , i ) , add( b[ i ] , a[ i ] , i ) ;
    For( i , 1 , n )
        if( !vis[ i ] )
            ++bel[ 0 ] , dep[ i ] = 1 , dfs( i ) ;
    getfa() ;
    solve() ;
 //   For( i , 1,  n ) cout << d[ 1 ][ i ] << " " << d[ 0 ][ i ] << " " << i << endl ;puts("") ;
    For( i , 1 , n )
        if( !vis[ i ] )
            dfs2( i , 0 ) ;
 //   For( i , 1 , m ) cout << c[ 0 ][ i ] << " " << c[ 1 ][ i ] << endl ;puts("") ;
  //  For( i , 1 , n ) cout << d[ 0 ][ i ] << " " << d[ 1 ][ i ] << endl ;
    int ans = 0 ;
    if( cnt[ 1 ] == 0 ) {
        printf("%d\n" , m ) ;
        For( i , 1 , m )
            printf("%d " , i ) ;
        return 0 ;
    }
    if( cnt[ 1 ] == 1 ) {
        For( i , 1 , m )
            if( c[ 1 ][ i ] == 1 && c[ 0 ][ i ] == 0 )
                    ans ++ ;
        printf("%d\n" , ans ) ;
        For( i , 1 , m )
            if( c[ 1 ][ i ] == 1 && c[ 0 ][ i ] == 0 )
                    printf("%d " , i ) ;
        return 0 ;
    }
    For( i , 1,  m )
        if( c[ 1 ][ i ] == cnt[ 1 ] && c[ 0 ][ i ] == 0 )
                ans ++ ;
    printf("%d\n" , ans ) ;
    For( i , 1 , m )
        if( c[ 1 ][ i ] == cnt[ 1 ] && c[ 0 ][ i ] == 0 )
            printf("%d " , i ) ;puts("") ;
    return 0 ;
}
/*
7 7
1 2
2 3
3 4
4 1
5 6
6 7
7 5

*/

2023/8/25 20:04
加载中...