#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++ )
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
49496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
65872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
59476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
