#include <iostream>
#include<vector>
#include<set>
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define int long long
const int N = 6e5 + 78 , inf = 1e19;
using namespace std;
string trans(int n , int k){
string s = "";
while(n != 0){
int d = n % k;
if(d < 10){
s = to_string(d) + s;
}
else{
s = char(d + 'A' - 10) + s;
}
n /= k;
}
return s;
}
int n , m , d[N] , q , sum = 0;
vector<pair<int , int>> g[N];
vector<int> ans;
int dj(int sta , int a1 , int a2 , int a3 , int a4){
for(int i = 0 ; i <= n ; i++)d[i] = inf;
d[sta] = 0;
int p[n + 1];
set<pair<int , int>> st;
st.insert({0 , sta});
while(st.size()){
int v = st.begin() -> second;
st.erase(st.begin());
for(int i = 0 ; i < g[v].size() ; i++){
int to = g[v][i].first , w = g[v][i].second;
int cur = d[v] + w;
if(d[to] > cur){
st.erase({d[to] , to});
d[to] = cur;
p[to] = v;
st.insert({d[to] , to});
}
}
}
return max(d[a1] , max(d[a2] , max(d[a3] , d[a4])));
}
void solve(){
cin >> n;
for(int i = 1 ; i < n ; i++){
int x, y , z;
cin >> x >> y >> z;
sum += z;
g[x].push_back({y , z});
g[y].push_back({x , z});
}
if(n != 5){
cin >> q;
while(q--){
int a1 , a2 , a3 , a4 , a5;
cin >> a1 >> a2 >> a3 >> a4 >> a5;
int mx = dj(a1 , a2 , a3 , a4 , a5);
mx = max(mx , dj(a2 , a3 , a4 , a5 , a1));
mx = max(mx , dj(a3 , a1 , a2 , a4 , a5));
mx = max(mx , dj(a4 , a1 , a2 , a3 , a5));
mx = max(mx , dj(a5 , a1 , a2 , a3 , a4));
cout << mx << '\n';
}
}
else{
cin >> q;
while(q--){
cout << sum << '\n';
}
}
}
main(){
Bekabot
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
Compilation message
roadsideadverts.cpp:9:32: warning: overflow in conversion from 'double' to 'long long int' changes value from '1.0e+19' to '9223372036854775807' [-Woverflow]
9 | const int N = 6e5 + 78 , inf = 1e19;
| ^~~~
roadsideadverts.cpp: In function 'long long int dj(long long int, long long int, long long int, long long int, long long int)':
roadsideadverts.cpp:38:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0 ; i < g[v].size() ; i++){
| ~~^~~~~~~~~~~~~
roadsideadverts.cpp:32:7: warning: variable 'p' set but not used [-Wunused-but-set-variable]
32 | int p[n + 1];
| ^
roadsideadverts.cpp: At global scope:
roadsideadverts.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
82 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
17492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
18096 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14292 KB |
Output is correct |
| 2 |
Execution timed out |
1080 ms |
17492 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
