oj.uz

Submission #58278

# Submission time Handle Problem Language Result Execution time Memory
58278 2018-07-17T10:46:06 Z evpipis 007 (CEOI14_007) C++14
23 / 100
 433 ms 17812 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", w1 - (d > c));
    else
        printf("%d\n", w1);
    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 5228 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 8 ms 5228 KB Output is correct
5 Correct 7 ms 5228 KB Output is correct
6 Partially correct 6 ms 5228 KB Partially correct
7 Partially correct 7 ms 5228 KB Partially correct
8 Correct 7 ms 5228 KB Output is correct
9 Partially correct 7 ms 5228 KB Partially correct
10 Correct 7 ms 5280 KB Output is correct
11 Correct 7 ms 5280 KB Output is correct
12 Correct 9 ms 5280 KB Output is correct
13 Partially correct 7 ms 5308 KB Partially correct
14 Correct 6 ms 5308 KB Output is correct
15 Partially correct 8 ms 5308 KB Partially correct
16 Correct 9 ms 5356 KB Output is correct
17 Correct 7 ms 5356 KB Output is correct
18 Correct 7 ms 5476 KB Output is correct
19 Partially correct 8 ms 5476 KB Partially correct
20 Partially correct 7 ms 5476 KB Partially correct
21 Correct 7 ms 5476 KB Output is correct
22 Partially correct 9 ms 5476 KB Partially correct
23 Partially correct 7 ms 5476 KB Partially correct
24 Correct 8 ms 5476 KB Output is correct

Subtask #2
14.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 46 ms 7164 KB Partially correct
2 Correct 63 ms 8188 KB Output is correct
3 Partially correct 67 ms 8188 KB Partially correct
4 Correct 58 ms 8188 KB Output is correct
5 Correct 43 ms 8188 KB Output is correct
6 Correct 37 ms 8188 KB Output is correct
7 Partially correct 39 ms 8188 KB Partially correct
8 Correct 57 ms 8188 KB Output is correct
9 Correct 92 ms 8188 KB Output is correct
10 Partially correct 292 ms 12412 KB Partially correct
11 Correct 90 ms 12412 KB Output is correct
12 Partially correct 112 ms 12412 KB Partially correct
13 Correct 140 ms 12412 KB Output is correct
14 Incorrect 74 ms 12412 KB Output isn't correct
15 Partially correct 95 ms 12412 KB Partially correct
16 Correct 135 ms 12412 KB Output is correct
17 Correct 80 ms 12412 KB Output is correct
18 Correct 92 ms 12412 KB Output is correct
19 Partially correct 131 ms 12412 KB Partially correct
20 Correct 411 ms 14672 KB Output is correct
21 Correct 174 ms 14672 KB Output is correct
22 Partially correct 126 ms 14672 KB Partially correct
23 Correct 200 ms 14672 KB Output is correct
24 Partially correct 226 ms 14672 KB Partially correct
25 Correct 196 ms 14672 KB Output is correct
26 Correct 165 ms 14672 KB Output is correct
27 Correct 129 ms 14672 KB Output is correct
28 Correct 150 ms 14672 KB Output is correct
29 Partially correct 273 ms 14672 KB Partially correct
30 Correct 306 ms 15208 KB Output is correct
31 Correct 214 ms 15208 KB Output is correct
32 Partially correct 150 ms 15208 KB Partially correct
33 Correct 134 ms 15208 KB Output is correct
34 Correct 166 ms 15208 KB Output is correct
35 Correct 140 ms 15208 KB Output is correct
36 Correct 147 ms 15208 KB Output is correct
37 Correct 211 ms 15208 KB Output is correct
38 Correct 180 ms 15208 KB Output is correct
39 Correct 270 ms 15208 KB Output is correct
40 Correct 433 ms 15740 KB Output is correct
41 Partially correct 426 ms 17812 KB Partially correct