Submission #625269

#	Time	Username	Problem	Language	Result	Execution time	Memory
625269		chonka	Senior Postmen (BOI14_postmen)	C++17	100 / 100	417 ms	70216 KiB

postmen

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 5e5 + 7 ;
bool used[ MAXN ] , aux[ MAXN ] ;
vector < int > v[ MAXN ] ;
pair < int , int > hh[ MAXN ] ;
vector < int > ord , stk ;

void dfs ( int x ) {
    while ( v[ x ].empty ( ) == false ) {
        int id = v[ x ].back ( ) ;
        v[ x ].pop_back ( ) ;
        if ( used[ id ] == false ) {
            used[ id ] = true ;
            dfs ( hh[ id ].first + hh[ id ].second - x ) ;
        }
    }
    ord.push_back ( x ) ;
}

void solve ( ) {
    int n , m ; cin >> n >> m ;
    for ( int i = 1 , x , y ; i <= m ; ++ i ) {
        cin >> x >> y ;
        hh[ i ] = { x , y } ;
        v[ x ].push_back ( i ) ;
        v[ y ].push_back ( i ) ;
    }
    dfs ( 1 ) ;
    for ( auto x : ord ) {
        if ( aux[ x ] == false ) {
            aux[ x ] = true ;
            stk.push_back ( x ) ;
        }
        else {
            cout << x ;
            while ( stk.back ( ) != x ) {
                int y = stk.back ( ) ; stk.pop_back ( ) ;
                cout << " " << y ;
                aux[ y ] = false ;
            }
            cout << "\n" ;
        }
    }
}

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

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45