oj.uz

Submission #65955

# Submission time Handle Problem Language Result Execution time Memory
65955 2018-08-09T07:14:38 Z ikura355 007 (CEOI14_007) C++14
30 / 100
 386 ms 17240 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 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]));
			}
		}
	}
}

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

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: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 Correct 6 ms 4984 KB Output is correct
2 Partially correct 6 ms 5112 KB Partially correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5184 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Partially correct 6 ms 5224 KB Partially correct
7 Partially correct 7 ms 5224 KB Partially correct
8 Correct 6 ms 5224 KB Output is correct
9 Partially correct 7 ms 5224 KB Partially correct
10 Partially correct 7 ms 5256 KB Partially correct
11 Partially correct 7 ms 5256 KB Partially correct
12 Correct 7 ms 5256 KB Output is correct
13 Partially correct 8 ms 5332 KB Partially correct
14 Correct 7 ms 5332 KB Output is correct
15 Partially correct 8 ms 5332 KB Partially correct
16 Correct 7 ms 5340 KB Output is correct
17 Correct 9 ms 5348 KB Output is correct
18 Correct 6 ms 5348 KB Output is correct
19 Partially correct 7 ms 5348 KB Partially correct
20 Partially correct 6 ms 5348 KB Partially correct
21 Partially correct 7 ms 5348 KB Partially correct
22 Partially correct 6 ms 5356 KB Partially correct
23 Partially correct 8 ms 5356 KB Partially correct
24 Correct 6 ms 5356 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 50 ms 7020 KB Partially correct
2 Correct 48 ms 7892 KB Output is correct
3 Partially correct 58 ms 7892 KB Partially correct
4 Correct 47 ms 7916 KB Output is correct
5 Partially correct 42 ms 7916 KB Partially correct
6 Partially correct 38 ms 7916 KB Partially correct
7 Partially correct 59 ms 7916 KB Partially correct
8 Partially correct 60 ms 7916 KB Partially correct
9 Correct 59 ms 7916 KB Output is correct
10 Partially correct 212 ms 12228 KB Partially correct
11 Correct 84 ms 12228 KB Output is correct
12 Partially correct 135 ms 12228 KB Partially correct
13 Correct 128 ms 12228 KB Output is correct
14 Correct 98 ms 12228 KB Output is correct
15 Partially correct 173 ms 12228 KB Partially correct
16 Partially correct 146 ms 12228 KB Partially correct
17 Partially correct 138 ms 12228 KB Partially correct
18 Correct 116 ms 12228 KB Output is correct
19 Partially correct 155 ms 12228 KB Partially correct
20 Correct 301 ms 13972 KB Output is correct
21 Correct 142 ms 13972 KB Output is correct
22 Partially correct 141 ms 13972 KB Partially correct
23 Partially correct 125 ms 13972 KB Partially correct
24 Partially correct 156 ms 13972 KB Partially correct
25 Correct 181 ms 13972 KB Output is correct
26 Partially correct 177 ms 13972 KB Partially correct
27 Partially correct 153 ms 13972 KB Partially correct
28 Partially correct 232 ms 13972 KB Partially correct
29 Partially correct 238 ms 13972 KB Partially correct
30 Correct 313 ms 14712 KB Output is correct
31 Correct 188 ms 14712 KB Output is correct
32 Partially correct 238 ms 14712 KB Partially correct
33 Partially correct 196 ms 14712 KB Partially correct
34 Correct 241 ms 14712 KB Output is correct
35 Correct 152 ms 14712 KB Output is correct
36 Correct 203 ms 14712 KB Output is correct
37 Partially correct 215 ms 14712 KB Partially correct
38 Partially correct 215 ms 14712 KB Partially correct
39 Partially correct 251 ms 14712 KB Partially correct
40 Correct 258 ms 15100 KB Output is correct
41 Partially correct 386 ms 17240 KB Partially correct