oj.uz

Submission #66073

# Submission time Handle Problem Language Result Execution time Memory
66073 2018-08-09T13:35:21 Z ikura355 007 (CEOI14_007) C++14
0 / 100
 411 ms 17276 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("-1");
	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 Partially correct 7 ms 5112 KB Partially correct
2 Incorrect 6 ms 5112 KB Output isn't correct
3 Partially correct 6 ms 5164 KB Partially correct
4 Partially correct 8 ms 5240 KB Partially correct
5 Partially correct 6 ms 5240 KB Partially correct
6 Incorrect 8 ms 5300 KB Output isn't correct
7 Incorrect 6 ms 5332 KB Output isn't correct
8 Partially correct 7 ms 5332 KB Partially correct
9 Incorrect 8 ms 5332 KB Output isn't correct
10 Incorrect 6 ms 5332 KB Output isn't correct
11 Incorrect 7 ms 5332 KB Output isn't correct
12 Incorrect 7 ms 5332 KB Output isn't correct
13 Incorrect 10 ms 5332 KB Output isn't correct
14 Incorrect 7 ms 5332 KB Output isn't correct
15 Incorrect 7 ms 5332 KB Output isn't correct
16 Incorrect 8 ms 5332 KB Output isn't correct
17 Incorrect 7 ms 5360 KB Output isn't correct
18 Incorrect 7 ms 5360 KB Output isn't correct
19 Incorrect 8 ms 5360 KB Output isn't correct
20 Incorrect 8 ms 5360 KB Output isn't correct
21 Incorrect 5 ms 5360 KB Output isn't correct
22 Incorrect 8 ms 5360 KB Output isn't correct
23 Incorrect 7 ms 5360 KB Output isn't correct
24 Partially correct 7 ms 5360 KB Partially correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 7024 KB Output isn't correct
2 Incorrect 65 ms 7860 KB Output isn't correct
3 Incorrect 46 ms 7860 KB Output isn't correct
4 Incorrect 59 ms 7956 KB Output isn't correct
5 Incorrect 35 ms 7956 KB Output isn't correct
6 Incorrect 35 ms 7956 KB Output isn't correct
7 Incorrect 60 ms 7956 KB Output isn't correct
8 Incorrect 47 ms 7956 KB Output isn't correct
9 Incorrect 71 ms 7956 KB Output isn't correct
10 Incorrect 220 ms 12204 KB Output isn't correct
11 Incorrect 73 ms 12204 KB Output isn't correct
12 Incorrect 93 ms 12204 KB Output isn't correct
13 Incorrect 75 ms 12204 KB Output isn't correct
14 Correct 61 ms 12204 KB Output is correct
15 Incorrect 108 ms 12204 KB Output isn't correct
16 Incorrect 99 ms 12204 KB Output isn't correct
17 Incorrect 81 ms 12204 KB Output isn't correct
18 Incorrect 92 ms 12204 KB Output isn't correct
19 Incorrect 152 ms 12204 KB Output isn't correct
20 Incorrect 264 ms 14004 KB Output isn't correct
21 Incorrect 146 ms 14004 KB Output isn't correct
22 Incorrect 118 ms 14004 KB Output isn't correct
23 Incorrect 147 ms 14004 KB Output isn't correct
24 Incorrect 134 ms 14004 KB Output isn't correct
25 Incorrect 149 ms 14004 KB Output isn't correct
26 Incorrect 128 ms 14004 KB Output isn't correct
27 Incorrect 138 ms 14004 KB Output isn't correct
28 Incorrect 189 ms 14004 KB Output isn't correct
29 Incorrect 234 ms 14004 KB Output isn't correct
30 Incorrect 293 ms 14828 KB Output isn't correct
31 Incorrect 160 ms 14828 KB Output isn't correct
32 Incorrect 224 ms 14828 KB Output isn't correct
33 Incorrect 159 ms 14828 KB Output isn't correct
34 Incorrect 171 ms 14828 KB Output isn't correct
35 Incorrect 136 ms 14828 KB Output isn't correct
36 Incorrect 149 ms 14828 KB Output isn't correct
37 Incorrect 186 ms 14828 KB Output isn't correct
38 Incorrect 242 ms 14828 KB Output isn't correct
39 Incorrect 222 ms 14828 KB Output isn't correct
40 Incorrect 286 ms 15104 KB Output isn't correct
41 Incorrect 411 ms 17276 KB Output isn't correct