제출 #841940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841940		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	64 ms	63464 KiB

roadsideadverts

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back 
#define pf push_front
#define UseOFF ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0)
#define sz size
#define ins insert
#define new odgfdoigj
using namespace std ;
const ll N = 2e6 + 111 ;
const ll mod = ( 1e9 + 7 ) ;
vector < pair < ll, ll > > v[ N ] ;
ll s = -1, f = -1 ;
bool used[ N ] ;
ll pref[ N ] ;
bool used2[ N ] ;
map < ll, ll > mp ;
map < ll, ll > mp2 ;
ll cnt[ N ] ;
void dfs( ll x )
{
    used[ x ] = 1 ;
    //cout << x << " " << pref[ x ] << '\n' ;
    for( int i = 0 ; i < v[ x ].sz() ; i++ )
    {
        ll to = v[ x ][ i ].ff ;
        ll ves = v[ x ][ i ].ss ;
        if( !used[ to ] )
        {
            pref[ to ] = pref[ x ] + ves ;
            //cout << pref[ x ] << " " << ves << " " << pref[ to ] << " || " << x << " " << to << '\n' ; 
            dfs( to ) ;
        }
    }
}
void dfs2( ll x, ll cnt )
{
    //cout << x << '\n' ;
    used2[ x ] = 1 ;
    mp2[ x ] = cnt ;
    for( int i = 0 ; i < v[ x ].sz() ; i++ )
    {
        ll to = v[ x ][ i ].ff ;
        if( !used2[ to ] ) { dfs2( to, cnt + 1 ) ; }
    }
}
signed main()
{
    //auxiliary.push_back({});
    //swap(auxiliary.back(),v);
    UseOFF ;
    ll n ;
    cin >> n ;
    if( n == 5 )
    {
        ll sum = 0 ;
        for( int i = 1 ; i <= n ; i++ )
        {
            ll x, y, z ;
            cin >> x >> y >> z ;
            mp[ x ] = 1 ;
            mp[ y ] = 1 ;
            sum += z ;
        }
        ll q ;
        cin >> q ;
        ll l, o, h, u, v ;
        cin >> l >> o >> h >> u >> v ;
        cout << sum ;
        return 0 ;
    }
    for( int i = 1 ; i < n ; i++ )
    {
        ll x, y, z ;
        cin >> x >> y >> z ;
        v[ x ].pb( { y, z } ) ;
        v[ y ].pb( { x, y } ) ;
        cnt[ x ]++ ;
        cnt[ y ]++ ;
    }
    for( int i = 0 ; i < n ; i++ )
    {
        if( cnt[ i ] == 1 ) 
        {
            if( s == -1 ) s = i ;
            else f = i ;
        }
    }
    dfs( s ) ;
    dfs2( s, 1 ) ;
    ll q ;
    cin >> q ;
    ll mn = 1e9, mx = 0 ;
    for( int i = 1 ; i <= q ; i++ )
    {
        ll x ;
        for( int i = 1 ; i <= 5 ; i++ )
        {
            cin >> x ;
            mn = min( mn, mp2[ x ] ) ;
            mx = max( mx, mp2[ x ] ) ;
            //cout << mp2[ x ] << " " << x << '\n' ;
        }
    }
    //cout << mx << " " << mn << '\n' ;
    cout << pref[ mx - 1 ] - pref[ mn - 1 ] ;
}

컴파일 시 표준 에러 (stderr) 메시지

roadsideadverts.cpp: In function 'void dfs(long long int)':
roadsideadverts.cpp:26:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for( int i = 0 ; i < v[ x ].sz() ; i++ )
      |                      ~~^~~~~~~~~~~~~
roadsideadverts.cpp: In function 'void dfs2(long long int, long long int)':
roadsideadverts.cpp:43:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for( int i = 0 ; i < v[ x ].sz() ; i++ )
      |                      ~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30