제출 #765053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765053		vjudge1	Roadside Advertisements (NOI17_roadsideadverts)	C++17	7 / 100	1078 ms	17676 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 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();
	}
}

컴파일 시 표준 에러 (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 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(){
      | ^~~~

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