oj.uz

Submission #58281

# Submission time Handle Problem Language Result Execution time Memory
58281 2018-07-17T10:48:37 Z evpipis 007 (CEOI14_007) C++
30 / 100
 425 ms 17920 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int len = 2e5+5, inf = 1e9;
int dis[4][len];
int n, m, s1, s2, t1, t2;
queue<int> myq;
vector<int> adj[len];

void bfs(int st, int t){
    for (int i = 1; i <= n; i++)
        dis[t][i] = -1;

    dis[t][st] = 0, myq.push(st);
    while (!myq.empty()){
        int u = myq.front();
        myq.pop();

        for (int j = 0; j < adj[u].size(); j++){
            int v = adj[u][j];
            if (dis[t][v] == -1)
                dis[t][v] = dis[t][u]+1, myq.push(v);
        }
    }
}

int main(){
    scanf("%d %d %d %d %d %d", &n, &m, &s1, &s2, &t1, &t2);
    for (int i = 0; i < m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].pb(b);
        adj[b].pb(a);
    }

    int a1, a2, b1, b2, w1, w2, c = 0, d = 0;
    bfs(t1, 0);
    a1 = dis[0][s1], b1 = dis[0][s2], w1 = b1-a1;

    bfs(t2, 1);
    a2 = dis[1][s1], b2 = dis[1][s2], w2 = b2-a2;

    if (w1 > w2)
        swap(a1, a2), swap(b1, b2), swap(w1, w2);

    bfs(s1, 2), bfs(s2, 3);
    for (int i = 1; i <= n; i++){
        if (dis[0][i] == dis[1][i] && dis[0][i]+dis[2][i] == dis[0][s1])
            c = max(c, dis[2][i]);
        if (dis[0][i] == dis[1][i] && dis[0][i]+dis[3][i] == dis[0][s2])
            d = max(d, dis[3][i]);
    }

    if (b1 == b2 && a1 == a2)
        printf("%d\n", max(w1 - (d > c), -1));
    else
        printf("%d\n", max(w1, -1));
    return 0;
}

/*
9 10
9 8 1 2
1 2
2 3
3 1
2 4
4 5
5 2
5 7
7 6
7 8
7 9

6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
*/

Compilation message

007.cpp: In function 'void bfs(int, int)':
007.cpp:26:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < adj[u].size(); j++){
                         ~~^~~~~~~~~~~~~~~
007.cpp: In function 'int main()':
007.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d %d", &n, &m, &s1, &s2, &t1, &t2);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5104 KB Output is correct
3 Correct 5 ms 5168 KB Output is correct
4 Correct 6 ms 5224 KB Output is correct
5 Correct 6 ms 5244 KB Output is correct
6 Partially correct 7 ms 5372 KB Partially correct
7 Partially correct 8 ms 5372 KB Partially correct
8 Correct 8 ms 5372 KB Output is correct
9 Partially correct 8 ms 5372 KB Partially correct
10 Correct 7 ms 5372 KB Output is correct
11 Correct 8 ms 5372 KB Output is correct
12 Correct 8 ms 5372 KB Output is correct
13 Partially correct 8 ms 5372 KB Partially correct
14 Correct 7 ms 5372 KB Output is correct
15 Partially correct 7 ms 5372 KB Partially correct
16 Correct 7 ms 5372 KB Output is correct
17 Correct 7 ms 5372 KB Output is correct
18 Correct 8 ms 5372 KB Output is correct
19 Partially correct 7 ms 5372 KB Partially correct
20 Partially correct 8 ms 5372 KB Partially correct
21 Correct 6 ms 5372 KB Output is correct
22 Partially correct 7 ms 5372 KB Partially correct
23 Partially correct 8 ms 5372 KB Partially correct
24 Correct 9 ms 5372 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 61 ms 7152 KB Partially correct
2 Correct 72 ms 8188 KB Output is correct
3 Partially correct 37 ms 8188 KB Partially correct
4 Correct 47 ms 8188 KB Output is correct
5 Correct 51 ms 8188 KB Output is correct
6 Correct 40 ms 8188 KB Output is correct
7 Partially correct 51 ms 8188 KB Partially correct
8 Correct 81 ms 8188 KB Output is correct
9 Correct 82 ms 8188 KB Output is correct
10 Partially correct 272 ms 12408 KB Partially correct
11 Correct 80 ms 12408 KB Output is correct
12 Partially correct 143 ms 12408 KB Partially correct
13 Correct 105 ms 12408 KB Output is correct
14 Correct 94 ms 12408 KB Output is correct
15 Partially correct 123 ms 12408 KB Partially correct
16 Correct 160 ms 12408 KB Output is correct
17 Correct 152 ms 12408 KB Output is correct
18 Correct 194 ms 12408 KB Output is correct
19 Partially correct 249 ms 12408 KB Partially correct
20 Correct 287 ms 14440 KB Output is correct
21 Correct 135 ms 14440 KB Output is correct
22 Partially correct 133 ms 14440 KB Partially correct
23 Correct 148 ms 14440 KB Output is correct
24 Partially correct 137 ms 14440 KB Partially correct
25 Correct 127 ms 14440 KB Output is correct
26 Correct 114 ms 14440 KB Output is correct
27 Correct 203 ms 14440 KB Output is correct
28 Correct 165 ms 14440 KB Output is correct
29 Partially correct 264 ms 14440 KB Partially correct
30 Correct 337 ms 15228 KB Output is correct
31 Correct 278 ms 15228 KB Output is correct
32 Partially correct 168 ms 15228 KB Partially correct
33 Correct 147 ms 15228 KB Output is correct
34 Correct 185 ms 15228 KB Output is correct
35 Correct 135 ms 15228 KB Output is correct
36 Correct 240 ms 15228 KB Output is correct
37 Correct 243 ms 15228 KB Output is correct
38 Correct 260 ms 15228 KB Output is correct
39 Correct 232 ms 15228 KB Output is correct
40 Correct 281 ms 15796 KB Output is correct
41 Partially correct 425 ms 17920 KB Partially correct