oj.uz

Submission #66075

# Submission time Handle Problem Language Result Execution time Memory
66075 2018-08-09T13:36:24 Z ikura355 007 (CEOI14_007) C++14
0 / 100
 430 ms 17236 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];
    return x<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");
	return !printf("0");
    int res = min(d[0][b]-d[0][a], d[1][b]-d[1][a]);
    if(res==0) return !printf("0");
//    printf("res = %d\n",res);
    if(d[0][a] == d[1][a] && d[0][b] == d[1][b]) {
        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 'int main()':
007.cpp:34: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:35: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:37: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 6 ms 4984 KB Output is correct
2 Incorrect 7 ms 5136 KB Output isn't correct
3 Correct 7 ms 5192 KB Output is correct
4 Correct 6 ms 5192 KB Output is correct
5 Correct 6 ms 5192 KB Output is correct
6 Incorrect 6 ms 5192 KB Output isn't correct
7 Incorrect 7 ms 5192 KB Output isn't correct
8 Correct 7 ms 5228 KB Output is correct
9 Incorrect 7 ms 5276 KB Output isn't correct
10 Incorrect 6 ms 5276 KB Output isn't correct
11 Partially correct 8 ms 5276 KB Partially correct
12 Incorrect 7 ms 5276 KB Output isn't correct
13 Incorrect 6 ms 5360 KB Output isn't correct
14 Incorrect 6 ms 5360 KB Output isn't correct
15 Incorrect 7 ms 5360 KB Output isn't correct
16 Incorrect 8 ms 5360 KB Output isn't correct
17 Incorrect 6 ms 5372 KB Output isn't correct
18 Incorrect 7 ms 5372 KB Output isn't correct
19 Incorrect 7 ms 5372 KB Output isn't correct
20 Incorrect 6 ms 5372 KB Output isn't correct
21 Incorrect 6 ms 5372 KB Output isn't correct
22 Incorrect 8 ms 5372 KB Output isn't correct
23 Incorrect 7 ms 5372 KB Output isn't correct
24 Correct 7 ms 5372 KB Output is correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 7032 KB Output isn't correct
2 Incorrect 45 ms 7800 KB Output isn't correct
3 Incorrect 43 ms 7800 KB Output isn't correct
4 Incorrect 62 ms 8056 KB Output isn't correct
5 Incorrect 45 ms 8056 KB Output isn't correct
6 Incorrect 46 ms 8056 KB Output isn't correct
7 Incorrect 39 ms 8056 KB Output isn't correct
8 Incorrect 45 ms 8056 KB Output isn't correct
9 Incorrect 67 ms 8056 KB Output isn't correct
10 Incorrect 365 ms 12252 KB Output isn't correct
11 Incorrect 126 ms 12252 KB Output isn't correct
12 Incorrect 125 ms 12252 KB Output isn't correct
13 Incorrect 96 ms 12252 KB Output isn't correct
14 Correct 81 ms 12252 KB Output is correct
15 Incorrect 107 ms 12252 KB Output isn't correct
16 Incorrect 100 ms 12252 KB Output isn't correct
17 Incorrect 107 ms 12252 KB Output isn't correct
18 Incorrect 88 ms 12252 KB Output isn't correct
19 Incorrect 143 ms 12252 KB Output isn't correct
20 Incorrect 281 ms 14028 KB Output isn't correct
21 Incorrect 137 ms 14028 KB Output isn't correct
22 Incorrect 137 ms 14028 KB Output isn't correct
23 Incorrect 150 ms 14028 KB Output isn't correct
24 Incorrect 156 ms 14028 KB Output isn't correct
25 Incorrect 128 ms 14028 KB Output isn't correct
26 Incorrect 113 ms 14028 KB Output isn't correct
27 Incorrect 152 ms 14028 KB Output isn't correct
28 Incorrect 227 ms 14028 KB Output isn't correct
29 Incorrect 185 ms 14028 KB Output isn't correct
30 Incorrect 290 ms 14656 KB Output isn't correct
31 Incorrect 186 ms 14656 KB Output isn't correct
32 Incorrect 135 ms 14656 KB Output isn't correct
33 Incorrect 131 ms 14656 KB Output isn't correct
34 Incorrect 205 ms 14656 KB Output isn't correct
35 Incorrect 168 ms 14656 KB Output isn't correct
36 Incorrect 174 ms 14656 KB Output isn't correct
37 Incorrect 163 ms 14656 KB Output isn't correct
38 Incorrect 170 ms 14656 KB Output isn't correct
39 Incorrect 183 ms 14656 KB Output isn't correct
40 Incorrect 285 ms 14972 KB Output isn't correct
41 Incorrect 430 ms 17236 KB Output isn't correct