Submission #765005

#	Time	Username	Problem	Language	Result	Execution time	Memory
765005		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	1081 ms	17716 KiB

roadsideadverts

#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;
		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])));
}
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;
		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';
	}
	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 (stderr)

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: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: At global scope:
roadsideadverts.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main(){
      | ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30