oj.uz

Submission #65954

# Submission time Handle Problem Language Result Execution time Memory
65954 2018-08-09T07:13:29 Z ikura355 007 (CEOI14_007) C++14
27 / 100
 410 ms 22192 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) assert(0);
        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
6.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 9848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Partially correct 7 ms 9920 KB Partially correct
3 Runtime error 12 ms 10176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 6 ms 10176 KB Output is correct
5 Correct 6 ms 10176 KB Output is correct
6 Partially correct 7 ms 10204 KB Partially correct
7 Partially correct 6 ms 10204 KB Partially correct
8 Correct 6 ms 10204 KB Output is correct
9 Partially correct 6 ms 10204 KB Partially correct
10 Partially correct 6 ms 10204 KB Partially correct
11 Partially correct 7 ms 10204 KB Partially correct
12 Correct 7 ms 10204 KB Output is correct
13 Partially correct 6 ms 10204 KB Partially correct
14 Correct 6 ms 10204 KB Output is correct
15 Partially correct 6 ms 10204 KB Partially correct
16 Correct 7 ms 10204 KB Output is correct
17 Correct 6 ms 10204 KB Output is correct
18 Correct 7 ms 10204 KB Output is correct
19 Partially correct 7 ms 10272 KB Partially correct
20 Partially correct 8 ms 10272 KB Partially correct
21 Partially correct 7 ms 10272 KB Partially correct
22 Partially correct 7 ms 10272 KB Partially correct
23 Partially correct 7 ms 10272 KB Partially correct
24 Correct 8 ms 10272 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 41 ms 12060 KB Partially correct
2 Correct 45 ms 12716 KB Output is correct
3 Partially correct 57 ms 12716 KB Partially correct
4 Correct 52 ms 12848 KB Output is correct
5 Partially correct 40 ms 12848 KB Partially correct
6 Partially correct 34 ms 12848 KB Partially correct
7 Partially correct 44 ms 12848 KB Partially correct
8 Partially correct 42 ms 12848 KB Partially correct
9 Correct 60 ms 12848 KB Output is correct
10 Partially correct 193 ms 17068 KB Partially correct
11 Correct 89 ms 17068 KB Output is correct
12 Partially correct 128 ms 17068 KB Partially correct
13 Correct 100 ms 17068 KB Output is correct
14 Correct 81 ms 17068 KB Output is correct
15 Partially correct 107 ms 17068 KB Partially correct
16 Partially correct 118 ms 17068 KB Partially correct
17 Partially correct 115 ms 17068 KB Partially correct
18 Correct 146 ms 17068 KB Output is correct
19 Partially correct 142 ms 17068 KB Partially correct
20 Correct 299 ms 18940 KB Output is correct
21 Correct 131 ms 18940 KB Output is correct
22 Partially correct 202 ms 18940 KB Partially correct
23 Partially correct 161 ms 18940 KB Partially correct
24 Partially correct 141 ms 18940 KB Partially correct
25 Correct 147 ms 18940 KB Output is correct
26 Partially correct 157 ms 18940 KB Partially correct
27 Partially correct 191 ms 18940 KB Partially correct
28 Partially correct 202 ms 18940 KB Partially correct
29 Partially correct 226 ms 18940 KB Partially correct
30 Correct 326 ms 19644 KB Output is correct
31 Correct 192 ms 19644 KB Output is correct
32 Partially correct 256 ms 19644 KB Partially correct
33 Partially correct 171 ms 19644 KB Partially correct
34 Correct 207 ms 19644 KB Output is correct
35 Correct 147 ms 19644 KB Output is correct
36 Correct 154 ms 19644 KB Output is correct
37 Partially correct 195 ms 19644 KB Partially correct
38 Partially correct 200 ms 19644 KB Partially correct
39 Partially correct 236 ms 19644 KB Partially correct
40 Correct 267 ms 20012 KB Output is correct
41 Partially correct 410 ms 22192 KB Partially correct