oj.uz

답안 #841962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
841962 2023-09-02T09:23:12 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 70 ms 65872 KB 
#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 ;
    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 ]++ ;
    }
    ll q ;
    cin >> q ;
    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

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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 49496 KB Output is correct

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 65872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 59476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 49496 KB Output is correct
2 Incorrect 70 ms 65872 KB Output isn't correct
3 Halted 0 ms 0 KB -