oj.uz

Submission #65971

# Submission time Handle Problem Language Result Execution time Memory
65971 2018-08-09T08:13:24 Z ikura355 007 (CEOI14_007) C++14
9 / 100
 19 ms 1100 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e3 + 5;
const int inf = 1e9;

struct node {
	int u,val;
	node(int _u = 0, int _val = 0) {
		u = _u; val = _val;
	}
	bool operator < (node a) const {
		return a.val<val;
	}
};

int n,m,a,b,s1,s2;
vector<int> way[maxn];
int len[maxn];
priority_queue<node> heap;
int d1[maxn], d2[maxn];

int sssp(int u, int ban = 0) {
	for(int i=1;i<=n;i++) len[i] = inf;
	len[u] = 0;
	heap.push(node(u,0));
	while(!heap.empty()) {
		auto t = heap.top(); heap.pop();
		int u = t.u, val = t.val;
		if(len[u]!=val) continue;
		for(auto v : way[u]) {
			if(v!=ban && len[v] > len[u] + 1) {
				len[v] = len[u] + 1;
				heap.push(node(v,len[v]));
			}
		}
	}
}

int main() {
	scanf("%d%d",&n,&m);
	scanf("%d%d%d%d",&a,&b,&s1,&s2);
	for(int i=1;i<=m;i++) {
		int u,v; scanf("%d%d",&u,&v);
		way[u].push_back(v); way[v].push_back(u);
	}
	sssp(a);
	for(int i=1;i<=n;i++) d1[i] = len[i];
	sssp(b);
	for(int i=1;i<=n;i++) d2[i] = len[i];
	if(d2[s1]<d1[s1] || d2[s2]<d1[s2]) printf("-1");
	else {
        int res = min(d2[s1]-d1[s1], d2[s2]-d1[s2]);
        sssp(b,a);
        int tmp = min(len[s1]-d1[s1], len[s2]-d1[s2]);
        if(tmp==res) printf("%d",res-1);
        else printf("%d",res);
	}
}

Compilation message

007.cpp: In function 'int sssp(int, int)':
007.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
007.cpp: In function 'int main()':
007.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
007.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&a,&b,&s1,&s2);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:44:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v; scanf("%d%d",&u,&v);
            ~~~~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 376 KB Partially correct
2 Partially correct 3 ms 376 KB Partially correct
3 Partially correct 2 ms 396 KB Partially correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 520 KB Output is correct
6 Partially correct 2 ms 548 KB Partially correct
7 Partially correct 2 ms 628 KB Partially correct
8 Correct 3 ms 628 KB Output is correct
9 Partially correct 2 ms 628 KB Partially correct
10 Partially correct 2 ms 628 KB Partially correct
11 Partially correct 2 ms 628 KB Partially correct
12 Correct 3 ms 720 KB Output is correct
13 Partially correct 2 ms 720 KB Partially correct
14 Correct 3 ms 720 KB Output is correct
15 Partially correct 2 ms 720 KB Partially correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 4 ms 740 KB Output is correct
18 Correct 3 ms 744 KB Output is correct
19 Partially correct 3 ms 744 KB Partially correct
20 Partially correct 3 ms 744 KB Partially correct
21 Partially correct 4 ms 744 KB Partially correct
22 Partially correct 3 ms 744 KB Partially correct
23 Correct 4 ms 744 KB Output is correct
24 Correct 3 ms 744 KB Output is correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 4 ms 908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 1036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 1036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 2 ms 1036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2 ms 1036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 1036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 2 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 2 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 2 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 2 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 3 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 3 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 19 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 3 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 4 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 3 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 3 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 2 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 2 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 3 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 3 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 3 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 3 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 4 ms 1100 KB Execution killed with signal 11 (could be triggered by violating memory limits)