oj.uz

Submission #65964

# Submission time Handle Problem Language Result Execution time Memory
65964 2018-08-09T07:47:06 Z ikura355 007 (CEOI14_007) C++14
0 / 100
 4 ms 1276 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) {
	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(len[v] > len[u] + 1) {
				len[v] = len[u] + 1;
				heap.push(node(v,len[v]));
			}
		}
	}
}

//bool check(int val) {
//    sssp(a,val);
//    for(int i=1;i<=n;i++) d1[i] = len[i];
//    sssp(b,0,a);
//    for(int i=1;i<=n;i++) d2[i] = len[i];
//    if(d2[s1]<d1[s1] || d2[s2]<d1[s2]) return 0;
//    return 1;
//}

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]);
        if(res==0) printf("0");
        else if((d1[s1]>d1[s2])!=(d2[s1]>d2[s2])) printf("%d",res-1);
        else printf("%d",res);
	}
}

Compilation message

007.cpp: In function 'int sssp(int)':
007.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
007.cpp: In function 'int main()':
007.cpp:50: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:51: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:53: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
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 416 KB Output is correct
4 Incorrect 3 ms 496 KB Output isn't correct
5 Incorrect 2 ms 548 KB Output isn't correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 2 ms 688 KB Output is correct
8 Incorrect 3 ms 688 KB Output isn't correct
9 Correct 2 ms 704 KB Output is correct
10 Partially correct 2 ms 704 KB Partially correct
11 Partially correct 2 ms 704 KB Partially correct
12 Incorrect 3 ms 704 KB Output isn't correct
13 Correct 2 ms 704 KB Output is correct
14 Incorrect 2 ms 704 KB Output isn't correct
15 Correct 2 ms 704 KB Output is correct
16 Incorrect 3 ms 704 KB Output isn't correct
17 Incorrect 3 ms 704 KB Output isn't correct
18 Incorrect 3 ms 704 KB Output isn't correct
19 Correct 3 ms 748 KB Output is correct
20 Correct 3 ms 756 KB Output is correct
21 Partially correct 2 ms 756 KB Partially correct
22 Correct 3 ms 756 KB Output is correct
23 Correct 3 ms 756 KB Output is correct
24 Incorrect 3 ms 756 KB Output isn't correct

Subtask #2
0.0 / 70.0

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