oj.uz

Submission #63931

# Submission time Handle Problem Language Result Execution time Memory
63931 2018-08-03T07:14:44 Z Scayre Evacuation plan (IZhO18_plan) C++14
23 / 100
 1978 ms 90200 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#include <set>
#include <cassert>
#define mp make_pair
#define pb push_back
#define ll long long
using namespace std;

const int MAXN = 1e6;
const int INF = 1e9 + 7;
vector <pair <int, int> > a[MAXN];
int dp[MAXN];
ll ans = 0;
set <pair <int, int> > SS;
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		a[x].pb(mp(y, w));
		a[y].pb(mp(x, w));
		SS.insert(mp(x, y));
		SS.insert(mp(y, x));
	}
	int A;
	scanf("%d", &A);
	for (int i = 1; i <= n; i++) {
		dp[i] = INF;
	}
	for (int i = 1; i <= A; i++) {
		int x;
		scanf("%d", &x);
		a[0].pb(mp(x, 0));
	}
	set <pair <int, int> > S;
	S.insert(mp(0, 0));
	while (!S.empty()) {
		int x = S.begin()->second;
		S.erase(S.begin());
		for (int i = 0; i < a[x].size(); i++) {
			int to = a[x][i].first;
			int w = a[x][i].second;
			if (dp[to] > dp[x] + w) {
				S.erase(mp(dp[to], to));
				dp[to] = dp[x] + w;
				S.insert(mp(dp[to], to));
			}
		}
	}
	int Q;
	scanf("%d", &Q);
	ll ans = 0;
	for (int i = 1; i <= Q; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		ans += min(dp[x], dp[y]);
		printf("%d\n", min(dp[x], dp[y]));
	}
	//cout << ans;


	return 0;
}

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:44:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a[x].size(); i++) {
                   ~~^~~~~~~~~~~~~
plan.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &A);
  ~~~~~^~~~~~~~~~
plan.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
plan.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
plan.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23844 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 25 ms 24056 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 25 ms 24056 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 23 ms 23804 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 26 ms 24032 KB Output is correct
10 Correct 25 ms 23928 KB Output is correct
11 Correct 25 ms 23928 KB Output is correct
12 Correct 24 ms 23928 KB Output is correct
13 Correct 25 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 24 ms 23928 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23844 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 25 ms 24056 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 25 ms 24056 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 23 ms 23804 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 26 ms 24032 KB Output is correct
10 Correct 25 ms 23928 KB Output is correct
11 Correct 25 ms 23928 KB Output is correct
12 Correct 24 ms 23928 KB Output is correct
13 Correct 25 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 24 ms 23928 KB Output is correct
16 Correct 287 ms 38640 KB Output is correct
17 Correct 1717 ms 90140 KB Output is correct
18 Correct 102 ms 29404 KB Output is correct
19 Correct 311 ms 42640 KB Output is correct
20 Correct 1802 ms 90144 KB Output is correct
21 Correct 663 ms 53724 KB Output is correct
22 Correct 272 ms 37752 KB Output is correct
23 Correct 1767 ms 90200 KB Output is correct
24 Correct 1728 ms 89988 KB Output is correct
25 Correct 1978 ms 90152 KB Output is correct
26 Correct 330 ms 42344 KB Output is correct
27 Correct 305 ms 42476 KB Output is correct
28 Correct 330 ms 42420 KB Output is correct
29 Correct 304 ms 42600 KB Output is correct
30 Correct 301 ms 42600 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 609 ms 52048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23844 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct
3 Correct 25 ms 24056 KB Output is correct
4 Correct 23 ms 23800 KB Output is correct
5 Correct 25 ms 24056 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 23 ms 23804 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 26 ms 24032 KB Output is correct
10 Correct 25 ms 23928 KB Output is correct
11 Correct 25 ms 23928 KB Output is correct
12 Correct 24 ms 23928 KB Output is correct
13 Correct 25 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 24 ms 23928 KB Output is correct
16 Correct 287 ms 38640 KB Output is correct
17 Correct 1717 ms 90140 KB Output is correct
18 Correct 102 ms 29404 KB Output is correct
19 Correct 311 ms 42640 KB Output is correct
20 Correct 1802 ms 90144 KB Output is correct
21 Correct 663 ms 53724 KB Output is correct
22 Correct 272 ms 37752 KB Output is correct
23 Correct 1767 ms 90200 KB Output is correct
24 Correct 1728 ms 89988 KB Output is correct
25 Correct 1978 ms 90152 KB Output is correct
26 Correct 330 ms 42344 KB Output is correct
27 Correct 305 ms 42476 KB Output is correct
28 Correct 330 ms 42420 KB Output is correct
29 Correct 304 ms 42600 KB Output is correct
30 Correct 301 ms 42600 KB Output is correct
31 Incorrect 23 ms 23800 KB Output isn't correct
32 Halted 0 ms 0 KB -