Submission #545190

#	Time	Username	Problem	Language	Result	Execution time	Memory
545190		chonka	Reconstruction Project (JOI22_reconstruction)	C++98	100 / 100	2312 ms	228076 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std ;

#define MAXN 501
#define MAXK 100007
#define inf 1000000007



int n , k ;
struct edge {
    int x , y , w ;
};
edge a[ MAXK ] ;

class uf {
public :
    short prv[ MAXN ] , rnk[ MAXN ] ;
    int edge_cnt ;
    void init ( ) {
        for ( int i = 1 ; i <= n ; ++ i ) {
            prv[ i ] = -1 , rnk[ i ] = 0 ;
        }
        edge_cnt = 0 ;
    }
    int get ( int x ) {
        if ( prv[ x ] == -1 ) { return x ; }
        int y = get ( prv[ x ] ) ;
        prv[ x ] = y ;
        return y ;
    }
    void unite ( int x , int y ) {
        int h1 = get ( x ) , h2 = get ( y ) ;
        if ( h1 != h2 ) {
            ++ edge_cnt ;
            if ( rnk[ h1 ] >= rnk[ h2 ] ) {
                rnk[ h1 ] += ( rnk[ h1 ] == rnk[ h2 ] ) ;
                prv[ h2 ] = h1 ;
            }
            else {
                prv[ h1 ] = h2 ;
            }
        }
    }
};

uf hh[ MAXK ] ;
int act[ MAXN ] ;



int range_st[ MAXK ] , range_en[ MAXK ] ;

struct event {
    int pos ;
    int chsum , chcoef ;
    event ( ) { pos = chsum = chcoef = 0 ; }
    event ( int _pos , int _chsum , int _chcoef ) {
        pos = _pos , chsum = _chsum , chcoef = _chcoef ;
    }
};
vector < event > srt ;

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    cin >> n >> k ;
    for ( int i = 1 ; i <= k ; ++ i ) {
        cin >> a[ i ].x >> a[ i ].y >> a[ i ].w ;
    }
    auto cmp = [ & ] ( edge p1 , edge p2 ) {
        return ( p1.w < p2.w ) ;
    };
    sort ( a + 1 , a + k + 1 , cmp ) ;
    for ( int i = 0 ; i <= k ; ++ i ) {
        hh[ i ].init ( ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        act[ i ] = 0 ;
    }
    for ( int i = 1 ; i <= k ; ++ i ) {
        range_st[ i ] = 0 ;
        for ( int j = 1 ; j < n ; ++ j ) {
            int id = act[ j ] ;
            if ( id == 0 ) { break ; }
            if ( hh[ id ].get ( a[ i ].x ) == hh[ id ].get ( a[ i ].y ) ) {
                range_st[ i ] = a[ id ].w ;
                break ;
            }
        }
        for ( int j = n - 2 ; j >= 1 ; -- j ) {
            int id = act[ j ] ;
            if ( id != 0 ) {
                hh[ id ].unite ( a[ i ].x , a[ i ].y ) ;
                if ( hh[ id ].edge_cnt > j ) {
                    act[ j + 1 ] = id ;
                }
            }
        }
        hh[ i ].unite ( a[ i ].x , a[ i ].y ) ;
        act[ 1 ] = i ;
    }
    for ( int i = 0 ; i <= k ; ++ i ) {
        hh[ i ].init ( ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        act[ i ] = 0 ;
    }

    for ( int i = k ; i >= 1 ; -- i ) {
        range_en[ i ] = inf ;
        for ( int j = 1 ; j < n ; ++ j ) {
            int id = act[ j ] ;
            if ( id == 0 ) { break ; }
            if ( hh[ id ].get ( a[ i ].x ) == hh[ id ].get ( a[ i ].y ) ) {
                range_en[ i ] = a[ id ].w ;
                break ;
            }
        }
        for ( int j = n - 2 ; j >= 1 ; -- j ) {
            int id = act[ j ] ;
            if ( id != 0 ) {
                hh[ id ].unite ( a[ i ].x , a[ i ].y ) ;
                if ( hh[ id ].edge_cnt > j ) {
                    act[ j + 1 ] = id ;
                }
            }
        }
        for ( int j = 1 ; j < n ; ++ j ) {
            int id = act[ j ] ;
            if ( id != 0 ) {
                hh[ id ].unite ( a[ i ].x , a[ i ].y ) ;
                if ( hh[ id ].edge_cnt > j ) {
                    act[ j + 1 ] = id ;
                }
            }
        }
        hh[ i ].unite ( a[ i ].x , a[ i ].y ) ;
        act[ 1 ] = i ;
    }


    for ( int i = 1 ; i <= k ; ++ i ) {
        // printf ( "%d %d %d --> %d %d\n" , a[ i ].x , a[ i ].y , a[ i ].w , range_st[ i ] , range_en[ i ] ) ;
        int st = range_st[ i ] ;
        if ( st != 0 ) {
            if ( ( ( a[ i ].w - st ) % 2 ) == 1 ) {
                ++ st ;
            }
            st = ( a[ i ].w + st ) / 2 ;
        }
        int en = range_en[ i ] ;
        if ( en != inf ) {
            if ( ( ( en - a[ i ].w ) % 2 ) == 0 ) {
                -- en ;
            }
            en = ( a[ i ].w + en ) / 2 ;
        }
        srt.push_back ( event ( st , a[ i ].w , -1 ) ) ;
        srt.push_back ( event ( a[ i ].w , -a[ i ].w , 1 ) ) ;

        srt.push_back ( event ( a[ i ].w , -a[ i ].w , 1 ) ) ;
        srt.push_back ( event ( en + 1 , a[ i ].w , -1 ) ) ;
    }
    auto ev_cmp = [ & ] ( event p1 , event p2 ) {
        return ( p1.pos < p2.pos ) ;
    };
    sort ( srt.begin ( ) , srt.end ( ) , ev_cmp ) ;
    int q ;
    cin >> q ;
    int lst = -1 ;
    int sz = srt.size ( ) ;
    long long totsm = 0 ;
    long long totcoef = 0 ;
    while ( q -- ) {
        int wh ; cin >> wh ;
        while ( lst + 1 < sz && srt[ lst + 1 ].pos <= wh ) {
            ++ lst ;
            totsm += srt[ lst ].chsum ;
            totcoef += srt[ lst ].chcoef ;
        }
        cout << totsm + totcoef * wh << "\n" ;
    }
    return 0 ;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23