oj.uz

Submission #671640

# Submission time Handle Problem Language Result Execution time Memory
671640 2022-12-13T12:04:11 Z smartmonky Evacuation plan (IZhO18_plan) C++14
41 / 100
 4000 ms 35232 KB 
#include <bits/stdc++.h>
  
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
using namespace std;
 
const int N = 1e5 + 10;
int d[N];
vector < pair <int,int> > g[N];
int n;
int dji(int f, int s){
	vector <int> dist(n + 1, -1e9);
	set <pair <int,int> > st;
	st.insert({0, f});
	dist[f] = d[f];
	while (!st.empty()) {
		int v = (--st.end())->second;
		st.erase (--st.end());
		if(v == s){
			return dist[v];
		}
		for (size_t j=0; j< g[v].size(); ++j) {
			int to = g[v][j].first;
			if (min(dist[v], d[to]) > dist[to]) {
				st.erase (make_pair (d[to], to));
				dist[to] = min(dist[v], d[to]);
				st.insert (make_pair (d[to], to));
			}
		}
	}
}
main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(d, 0x3f3f, sizeof(d));
	int m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	int k;
	cin >> k;
	set <pair <int,int> > st;
	for(int i = 0; i < k; i++){
		int a;
		cin >> a;
		st.insert({0, a});
		d[a] = 0;
	}
	while (!st.empty()) {
		int v = st.begin()->second;
		st.erase (st.begin());
		for (size_t j=0; j<g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
				d[to] = d[v] + len;
				st.insert (make_pair (d[to], to));
			}
		}
	}
	int q;
	cin >> q;
	while(q--){
		int a, b;
		cin >> a >> b;
		cout << dji(a,b) << endl;
	}
}

Compilation message

plan.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main(){
      | ^~~~
plan.cpp: In function 'long long int dji(long long int, long long int)':
plan.cpp:16:31: warning: control reaches end of non-void function [-Wreturn-type]
   16 |  vector <int> dist(n + 1, -1e9);
      |                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 118 ms 3540 KB Output is correct
3 Correct 108 ms 3540 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 109 ms 3540 KB Output is correct
6 Correct 113 ms 3540 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 8 ms 3412 KB Output is correct
10 Correct 6 ms 3540 KB Output is correct
11 Correct 9 ms 3528 KB Output is correct
12 Correct 109 ms 3540 KB Output is correct
13 Correct 8 ms 3412 KB Output is correct
14 Correct 6 ms 3412 KB Output is correct
15 Correct 7 ms 3412 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 118 ms 3540 KB Output is correct
3 Correct 108 ms 3540 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 109 ms 3540 KB Output is correct
6 Correct 113 ms 3540 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 8 ms 3412 KB Output is correct
10 Correct 6 ms 3540 KB Output is correct
11 Correct 9 ms 3528 KB Output is correct
12 Correct 109 ms 3540 KB Output is correct
13 Correct 8 ms 3412 KB Output is correct
14 Correct 6 ms 3412 KB Output is correct
15 Correct 7 ms 3412 KB Output is correct
16 Execution timed out 4051 ms 10640 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 17212 KB Output is correct
2 Correct 514 ms 34892 KB Output is correct
3 Correct 490 ms 34800 KB Output is correct
4 Correct 48 ms 8808 KB Output is correct
5 Correct 488 ms 34880 KB Output is correct
6 Correct 432 ms 34896 KB Output is correct
7 Correct 482 ms 34976 KB Output is correct
8 Correct 467 ms 34824 KB Output is correct
9 Correct 425 ms 35048 KB Output is correct
10 Correct 482 ms 34808 KB Output is correct
11 Correct 507 ms 34896 KB Output is correct
12 Correct 493 ms 34956 KB Output is correct
13 Correct 493 ms 34892 KB Output is correct
14 Correct 480 ms 35052 KB Output is correct
15 Correct 503 ms 35232 KB Output is correct
16 Correct 500 ms 35012 KB Output is correct
17 Correct 437 ms 35048 KB Output is correct
18 Correct 471 ms 34892 KB Output is correct
19 Correct 41 ms 8916 KB Output is correct
20 Correct 477 ms 34964 KB Output is correct
21 Correct 381 ms 32588 KB Output is correct
22 Correct 133 ms 15144 KB Output is correct
23 Correct 66 ms 9320 KB Output is correct
24 Correct 131 ms 15152 KB Output is correct
25 Correct 127 ms 15068 KB Output is correct
26 Correct 68 ms 9816 KB Output is correct
27 Correct 48 ms 8864 KB Output is correct
28 Correct 132 ms 15104 KB Output is correct
29 Correct 48 ms 8824 KB Output is correct
30 Correct 133 ms 15136 KB Output is correct
31 Correct 46 ms 8824 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 118 ms 3540 KB Output is correct
3 Correct 108 ms 3540 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 109 ms 3540 KB Output is correct
6 Correct 113 ms 3540 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 8 ms 3412 KB Output is correct
10 Correct 6 ms 3540 KB Output is correct
11 Correct 9 ms 3528 KB Output is correct
12 Correct 109 ms 3540 KB Output is correct
13 Correct 8 ms 3412 KB Output is correct
14 Correct 6 ms 3412 KB Output is correct
15 Correct 7 ms 3412 KB Output is correct
16 Execution timed out 4051 ms 10640 KB Time limit exceeded
17 Halted 0 ms 0 KB -