oj.uz

답안 #764979

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764979 2023-06-24T07:07:23 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 1000 ms 18096 KB 
#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(){
      | ^~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14292 KB Output is correct

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1080 ms 17492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1070 ms 18096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 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 -