oj.uz

Submission #765146

# Submission time Handle Problem Language Result Execution time Memory
765146 2023-06-24T08:44:42 Z vjudge1 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 1000 ms 15764 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 = 5e5 + 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 fin){
		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[fin];
}
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;
	while(q--){
		int a[6] , mx = 0;
		cin >> a[1] >> a[2] >> a[3] >> a[4] >> a[5];
		for(int i = 1 ; i <= 5 ; i++){
			for(int j = 1 ; j <= 5 ; j++){
				if(i != j)mx = max(mx , dj(a[i] , a[j]));
			}
		}
		cout << mx << '\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 = 5e5 + 78 , inf = 1e19;
      |                                ^~~~
roadsideadverts.cpp: In function 'long long int dj(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:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main(){
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 15020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 15764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Execution timed out 1059 ms 15020 KB Time limit exceeded
3 Halted 0 ms 0 KB -