oj.uz

Submission #66074

# Submission time Handle Problem Language Result Execution time Memory
66074 2018-08-09T13:35:54 Z ikura355 007 (CEOI14_007) C++14
0 / 100
 418 ms 17188 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);
	return !printf("0");
	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]);
    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 7 ms 4984 KB Output is correct
2 Incorrect 8 ms 5100 KB Output isn't correct
3 Correct 7 ms 5100 KB Output is correct
4 Correct 8 ms 5132 KB Output is correct
5 Correct 6 ms 5184 KB Output is correct
6 Incorrect 6 ms 5184 KB Output isn't correct
7 Incorrect 7 ms 5232 KB Output isn't correct
8 Correct 7 ms 5384 KB Output is correct
9 Incorrect 8 ms 5384 KB Output isn't correct
10 Incorrect 6 ms 5384 KB Output isn't correct
11 Partially correct 7 ms 5384 KB Partially correct
12 Incorrect 6 ms 5384 KB Output isn't correct
13 Incorrect 9 ms 5384 KB Output isn't correct
14 Incorrect 6 ms 5384 KB Output isn't correct
15 Incorrect 7 ms 5384 KB Output isn't correct
16 Incorrect 9 ms 5384 KB Output isn't correct
17 Incorrect 9 ms 5384 KB Output isn't correct
18 Incorrect 7 ms 5384 KB Output isn't correct
19 Incorrect 7 ms 5384 KB Output isn't correct
20 Incorrect 8 ms 5384 KB Output isn't correct
21 Incorrect 8 ms 5384 KB Output isn't correct
22 Incorrect 8 ms 5384 KB Output isn't correct
23 Incorrect 7 ms 5384 KB Output isn't correct
24 Correct 10 ms 5384 KB Output is correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 7036 KB Output isn't correct
2 Incorrect 55 ms 7892 KB Output isn't correct
3 Incorrect 59 ms 7892 KB Output isn't correct
4 Incorrect 53 ms 7932 KB Output isn't correct
5 Incorrect 33 ms 7932 KB Output isn't correct
6 Incorrect 44 ms 7932 KB Output isn't correct
7 Incorrect 46 ms 7932 KB Output isn't correct
8 Incorrect 48 ms 7932 KB Output isn't correct
9 Incorrect 61 ms 7932 KB Output isn't correct
10 Incorrect 259 ms 12164 KB Output isn't correct
11 Incorrect 94 ms 12164 KB Output isn't correct
12 Incorrect 115 ms 12164 KB Output isn't correct
13 Incorrect 89 ms 12164 KB Output isn't correct
14 Incorrect 85 ms 12164 KB Output isn't correct
15 Incorrect 117 ms 12164 KB Output isn't correct
16 Incorrect 106 ms 12164 KB Output isn't correct
17 Incorrect 115 ms 12164 KB Output isn't correct
18 Incorrect 115 ms 12164 KB Output isn't correct
19 Incorrect 186 ms 12164 KB Output isn't correct
20 Incorrect 376 ms 14100 KB Output isn't correct
21 Incorrect 167 ms 14100 KB Output isn't correct
22 Incorrect 126 ms 14100 KB Output isn't correct
23 Incorrect 161 ms 14100 KB Output isn't correct
24 Incorrect 181 ms 14100 KB Output isn't correct
25 Incorrect 139 ms 14100 KB Output isn't correct
26 Incorrect 150 ms 14100 KB Output isn't correct
27 Incorrect 139 ms 14100 KB Output isn't correct
28 Incorrect 157 ms 14100 KB Output isn't correct
29 Incorrect 232 ms 14100 KB Output isn't correct
30 Incorrect 347 ms 14744 KB Output isn't correct
31 Incorrect 173 ms 14744 KB Output isn't correct
32 Incorrect 178 ms 14744 KB Output isn't correct
33 Incorrect 167 ms 14744 KB Output isn't correct
34 Incorrect 231 ms 14744 KB Output isn't correct
35 Incorrect 171 ms 14744 KB Output isn't correct
36 Incorrect 168 ms 14744 KB Output isn't correct
37 Incorrect 219 ms 14744 KB Output isn't correct
38 Incorrect 205 ms 14744 KB Output isn't correct
39 Incorrect 199 ms 14744 KB Output isn't correct
40 Incorrect 295 ms 15100 KB Output isn't correct
41 Incorrect 418 ms 17188 KB Output isn't correct