QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#132488#6560. Broken Minimum Spanning TreeSorting#RE 1ms3600kbC++202.7kb2023-07-30 00:28:572023-07-30 00:29:00

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-30 00:29:00]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3600kb
  • [2023-07-30 00:28:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 3007 ;


int n , m ;
struct edge {
    int x , y , len ;
};
edge a[ MAXN ] ;
int srt[ MAXN ] ;

bool opt[ MAXN ] ;
int prv[ MAXN ] , rnk[ MAXN ] ;

int get ( int x ) {
    if ( prv[ x ] == -1 ) { return x ; }
    int y = get ( prv[ x ] ) ;
    prv[ x ] = y ;
    return y ;
}

bool unite ( int x , int y ) {
    int k1 = get ( x ) , k2 = get ( y ) ;
    if ( k1 == k2 ) { return false ; }
    if ( rnk[ k1 ] < rnk[ k2 ] ) { swap ( k1 , k2 ) ; }
    rnk[ k1 ] += ( rnk[ k1 ] == rnk[ k2 ] ) ;
    prv[ k2 ] = k1 ;
    return true ;
}


int foo_prv[ MAXN ] , foo_rnk[ MAXN ] ;

void solve ( ) {
    cin >> n >> m ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        cin >> a[ i ].x >> a[ i ].y >> a[ i ].len ;
        srt[ i ] = i ;
    }
    auto cmp = [ & ] ( int x , int y ) {
        if ( a[ x ].len != a[ y ].len ) { return ( a[ x ].len < a[ y ].len ) ; }
        return ( x < y ) ; 
    };
    sort ( srt + 1 , srt + m + 1 , cmp ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        prv[ i ] = -1 , rnk[ i ] = 0 ;
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        opt[ srt[ i ] ] = unite ( a[ srt[ i ] ].x , a[ srt[ i ] ].y ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        prv[ i ] = -1 , rnk[ i ] = 0 ;
    }
    vector < pii > ret ;
    for ( int i = 1 ; i <= n - 1 ; ++ i ) {
        if ( opt[ i ] == true ) { unite ( a[ i ].x , a[ i ].y ) ; }
    }
    for ( int i = 1 ; i <= n - 1 ; ++ i ) {
        if ( opt[ i ] == true ) { continue ; }
        for ( int j = 1 ; j <= n ; ++ j ) {
            foo_prv[ j ] = prv[ j ] ;
            foo_rnk[ j ] = rnk[ j ] ;
        }
        for ( int j = i + 1 ; j <= n - 1 ; ++ j ) {
            unite ( a[ j ].x , a[ j ].y ) ;
        }
        for ( int j = n ; j <= m ; ++ j ) {
            if ( opt[ j ] == true && get ( a[ j ].x ) != get ( a[ j ].y ) ) {
                ret.push_back ( { i , j } ) ;
                break ;
            }
        }
        for ( int j = 1 ; j <= n ; ++ j ) {
            prv[ j ] = foo_prv[ j ] ;
            rnk[ j ] = foo_rnk[ j ] ;
        }
        auto [ x , y ] = ret.back ( ) ;
        unite ( x , y ) ;
    }
    cout << (int)ret.size ( ) << "\n" ;
    for ( auto [ x , y ] : ret ) {
        cout << x << " " << y << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}


詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3600kb

input:

4 4
1 2 10
2 3 3
3 4 1
1 4 4

output:

1
1 4

result:

ok correct!

Test #2:

score: -100
Runtime Error

input:

6 8
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10
1 3 1
4 6 1

output:


result: