#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 dj1(int sta , int a1 , int a2 , int a3 , int a4){
for(int i = 0 ; i <= n ; i++)d[i] = inf;
d[sta] = 0;
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;
st.insert({d[to] , to});
}
}
}
return max(d[a1] , max(d[a2] , max(d[a3] , d[a4])));
}
int dj2(int sta , int a1 , int a2 , int a3){
for(int i = 0 ; i <= n ; i++)d[i] = inf;
d[sta] = 0;
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;
st.insert({d[to] , to});
}
}
}
return max(d[a1] , max(d[a2] , d[a3]));
}
int dj3(int sta , int a1 , int a2){
for(int i = 0 ; i <= n ; i++)d[i] = inf;
d[sta] = 0;
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;
st.insert({d[to] , to});
}
}
}
return max(d[a1] , d[a2]);
}
int dj4(int sta , int a1){
for(int i = 0 ; i <= n ; i++)d[i] = inf;
d[sta] = 0;
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;
st.insert({d[to] , to});
}
}
}
return d[a1];
}
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});
}
cin >> q;
if(n != 5){
while(q--){
int a1 , a2 , a3 , a4 , a5;
cin >> a1 >> a2 >> a3 >> a4 >> a5;
cout << max(dj4(a4 , a5) , max(dj3(a3 , a4 , a5) , max(dj2(a2 , a3 , a4 , a5) , dj1(a1 , a2 , a3 , a4 , a5)))) << '\n';
}
return;
}
else{
while(q--){
int a1 , a2 , a3 , a4 , a5;
cin >> a1 >> a2 >> a3 >> a4 >> a5;
cout << sum << '\n';
}
return;
}
}
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 dj1(long long int, long long int, long long int, long long int, long long int)':
roadsideadverts.cpp:37: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]
37 | for(int i = 0 ; i < g[v].size() ; i++){
| ~~^~~~~~~~~~~~~
roadsideadverts.cpp: In function 'long long int dj2(long long int, long long int, long long int, long long int)':
roadsideadverts.cpp:57: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]
57 | for(int i = 0 ; i < g[v].size() ; i++){
| ~~^~~~~~~~~~~~~
roadsideadverts.cpp: In function 'long long int dj3(long long int, long long int, long long int)':
roadsideadverts.cpp:77: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]
77 | for(int i = 0 ; i < g[v].size() ; i++){
| ~~^~~~~~~~~~~~~
roadsideadverts.cpp: In function 'long long int dj4(long long int, long long int)':
roadsideadverts.cpp:97: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]
97 | for(int i = 0 ; i < g[v].size() ; i++){
| ~~^~~~~~~~~~~~~
roadsideadverts.cpp: At global scope:
roadsideadverts.cpp:138:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
138 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
17040 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
17676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Execution timed out |
1073 ms |
17040 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
