oj.uz

Submission #842058

# Submission time Handle Problem Language Result Execution time Memory
842058 2023-09-02T10:54:13 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 54 ms 10584 KB 
#include <bits/stdc++.h>
#define ll int
#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 = 50011 ;
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 ] ;
ll X[ N ], Y[ N ], Z[ N ] ;
void dfs( ll x )
{
    used[ x ] = 1 ;
    //cout << x << " " << pref[ x ] << " " << "ybunijmok,l " << '\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 ;
    ll sum = 0 ;
    for( int i = 1 ; i < n ; i++ )
    {
        cin >> X[ i ] >> Y[ i ] >> Z[ i ] ;
        sum += Z[ i ] ;
        v[ X[ i ] ].pb( { Y[ i ], Z[ i ] } ) ;
        v[ Y[ i ] ].pb( { X[ i ], Z[ i ] } ) ;
        cnt[ X[ i ] ]++ ;
        cnt[ Y[ i ] ]++ ;
    }
    ll q ;
    cin >> q ;
    if( n == 5 && q == 1 )
    {
        cout << sum ;
        return 0 ;
    }
    ll s = 0 ;
    for( int i = 0 ; i < n ; i++ )
    {
        if( cnt[ i ] == 1 ) 
        {
            s = i ;
            dfs2( s, 1 ) ;
            break ;
        }
    }
    for( int i = 0 ; i < n ; i++ )
    {
        //cout << i << " " << mp2[ i ] << '\n' ;
    }
    for( int i = 0 ; i < n ; i++ ) v[ i ].clear() ;
    for( int i = 0 ; i < n ; i++ )
    {
        X[ i ] = mp2[ X[ i ] ] ;
        Y[ i ] = mp2[ Y[ i ] ] ;
        v[ X[ i ] ].pb( { Y[ i ], Z[ i ] } ) ;
        v[ Y[ i ] ].pb( { X[ i ], Z[ i ] } ) ;
    }
    dfs( mp2[ 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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 8020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 54 ms 10584 KB Output isn't correct
3 Halted 0 ms 0 KB -