oj.uz

Submission #66065

# Submission time Handle Problem Language Result Execution time Memory
66065 2018-08-09T13:24:09 Z ikura355 007 (CEOI14_007) C++14
10 / 100
 607 ms 56520 KB 
#include<bits/stdc++.h>
using namespace std;

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

int n,m,a,b,s1,s2;
vector<int> way[maxn];
int d[2][maxn];
int q[maxn];
int p[maxn], wow[maxn];

int sssp(int k, int u) {
    int l = 1, r = 0;
	for(int i=1;i<=n;i++) d[k][i] = inf;
	d[k][u] = 0; q[++r] = u;
	while(l<=r) {
		int u = q[l++];
		for(auto v : way[u]) {
			if(d[k][v] > d[k][u] + 1) {
				d[k][v] = d[k][u] + 1; q[++r] = v;
			}
		}
	}
}

bool cmp(int x, int y) {
    if(d[0][x]!=d[0][y]) return d[0][x] < d[0][y];
    if(d[1][x]!=d[1][y]) return d[1][x] < d[1][y];
}

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(0,s1); sssp(1,s2);
	if(d[0][a]>d[0][b] || d[1][a]>d[1][b]) return !printf("-1");
    int res = min(d[0][b]-d[0][a], d[1][b]-d[1][a]);
//    printf("res = %d\n",res);
    if(d[0][b]-d[0][a] == d[1][b]-d[1][a]) {
        for(int i=1;i<=n;i++) p[i] = i;
        sort(&p[1],&p[n],cmp);
        for(int i=1;i<=n;i++) {
            int u = p[i];
            for(auto v : way[u]) {
                if(d[0][v]==d[0][u]+1 && d[1][v]==d[1][u]+1) wow[v] = max(wow[v], wow[u]+1);
            }
//            printf("wow %d = %d\n",u,wow[u]);
        }
        if(wow[a]+res<wow[b]) res = res-1;
    }
    printf("%d",res);
}

Compilation message

007.cpp: In function 'int sssp(int, int)':
007.cpp:25:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
007.cpp: In function 'bool cmp(int, int)':
007.cpp:30:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
007.cpp: In function 'int main()':
007.cpp:33: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:34: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:36: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
10.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 8 ms 5224 KB Output is correct
3 Correct 8 ms 5224 KB Output is correct
4 Incorrect 8 ms 5224 KB Output isn't correct
5 Correct 8 ms 5224 KB Output is correct
6 Correct 9 ms 5224 KB Output is correct
7 Correct 9 ms 5264 KB Output is correct
8 Correct 9 ms 5264 KB Output is correct
9 Correct 8 ms 5312 KB Output is correct
10 Correct 8 ms 5340 KB Output is correct
11 Correct 8 ms 5368 KB Output is correct
12 Correct 8 ms 5368 KB Output is correct
13 Correct 10 ms 5404 KB Output is correct
14 Correct 8 ms 5404 KB Output is correct
15 Correct 8 ms 5404 KB Output is correct
16 Correct 7 ms 5420 KB Output is correct
17 Correct 9 ms 5420 KB Output is correct
18 Correct 8 ms 5436 KB Output is correct
19 Correct 10 ms 5444 KB Output is correct
20 Correct 8 ms 5452 KB Output is correct
21 Correct 7 ms 5460 KB Output is correct
22 Correct 8 ms 5468 KB Output is correct
23 Correct 7 ms 5476 KB Output is correct
24 Runtime error 16 ms 10348 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 12876 KB Output is correct
2 Incorrect 67 ms 14420 KB Output isn't correct
3 Correct 124 ms 14420 KB Output is correct
4 Correct 64 ms 15772 KB Output is correct
5 Correct 47 ms 15772 KB Output is correct
6 Correct 32 ms 15772 KB Output is correct
7 Correct 88 ms 16700 KB Output is correct
8 Correct 102 ms 17388 KB Output is correct
9 Runtime error 66 ms 21296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 275 ms 35288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 156 ms 35288 KB Output is correct
12 Runtime error 127 ms 35968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 221 ms 35968 KB Output is correct
14 Correct 65 ms 35968 KB Output is correct
15 Correct 206 ms 38512 KB Output is correct
16 Correct 110 ms 39260 KB Output is correct
17 Correct 267 ms 40872 KB Output is correct
18 Correct 289 ms 42152 KB Output is correct
19 Runtime error 178 ms 43952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 272 ms 49780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Correct 192 ms 49780 KB Output is correct
22 Correct 330 ms 49780 KB Output is correct
23 Correct 213 ms 49780 KB Output is correct
24 Correct 219 ms 49780 KB Output is correct
25 Correct 278 ms 49780 KB Output is correct
26 Correct 259 ms 49780 KB Output is correct
27 Correct 312 ms 49780 KB Output is correct
28 Correct 463 ms 49780 KB Output is correct
29 Runtime error 237 ms 49780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 359 ms 51232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Correct 241 ms 51232 KB Output is correct
32 Correct 425 ms 51232 KB Output is correct
33 Correct 280 ms 51232 KB Output is correct
34 Correct 447 ms 51232 KB Output is correct
35 Correct 193 ms 51232 KB Output is correct
36 Correct 212 ms 51232 KB Output is correct
37 Correct 229 ms 51232 KB Output is correct
38 Correct 360 ms 51232 KB Output is correct
39 Correct 607 ms 51232 KB Output is correct
40 Runtime error 240 ms 52372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 360 ms 56520 KB Execution killed with signal 11 (could be triggered by violating memory limits)