Submission #841963

#	Time	Username	Problem	Language	Result	Execution time	Memory
841963		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	59 ms	67984 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[ mp2[ to ] ] = pref[ mp2[ x ] ] + ves ;
            //cout << pref[ mp2[ x ] ] << " " << ves << " " << pref[ mp2[ to ] ] << " || " << mp2[ x ] << " " << mp2[ 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 ;
    ll sum = 0 ;
    for( int i = 1 ; i < n ; i++ )
    {
        ll x, y, z ;
        cin >> x >> y >> z ;
        sum += z ;
        v[ x ].pb( { y, z } ) ;
        v[ y ].pb( { x, y } ) ;
        cnt[ x ]++ ;
        cnt[ y ]++ ;
    }
    ll q ;
    cin >> q ;
    if( n == 5 && q == 1 )
    {
        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 ]++ ;
    }
    ll s = 0 ;
    for( int i = 0 ; i < n ; i++ )
    {
        if( cnt[ i ] == 1 ) 
        {
            s = i ;
            dfs2( s, 1 ) ;
            break ;
        }
    }
    dfs( s ) ;
    ll mn = 1e9, mx = 0 ;
    for( int i = 1 ; i <= q ; i++ )
    {
        for( int j = 1 ; j <= 5 ; j++ )
        {
            ll x ;
            cin >> x ;
            mn = min( mn, mp2[ x ] ) ;
            mx = max( mx, mp2[ x ] ) ;
        }
        cout << pref[ mx ] - pref[ mn ] << '\n' ;
    }
}

Compilation message (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