oj.uz

Submission #58251

# Submission time Handle Problem Language Result Execution time Memory
58251 2018-07-17T09:16:47 Z evpipis 007 (CEOI14_007) C++14
0 / 100
 907 ms 16620 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[len], tim[len];
int n, m, s1, s2, t1, t2;
queue<int> myq;
vector<int> adj[len];
bool check(int x){
    for (int i = 1; i <= n; i++)
        dis[i] = inf;

    if (0 < tim[s2]+x)
        dis[s2] = 0, myq.push(s2);
    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[v] == inf)// && dis[u]+1 < tim[v]+x)
                dis[v] = dis[u]+1, myq.push(v);
        }
    }

    return !(dis[t1] < tim[t1]+x || dis[t2] < tim[t2]+x);
}

int bs(){
    int l = 0, r = n, ans = -1;
    while (l <= r){
        int mid = (l+r)/2;
        if (check(mid))
            l = mid+1, ans = mid;
        else
            r = mid-1;
    }

    return ans;
}

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);
    }

    for (int i = 1; i <= n; i++)
        tim[i] = -1;

    tim[s1] = 0, myq.push(s1);
    while (!myq.empty()){
        int u = myq.front();
        myq.pop();

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

    printf("%d\n", bs());
    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
*/

Compilation message

007.cpp: In function 'bool check(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:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < adj[u].size(); j++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:50: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:53: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
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5288 KB Output is correct
4 Incorrect 6 ms 5352 KB Output isn't correct
5 Incorrect 6 ms 5352 KB Output isn't correct
6 Correct 6 ms 5352 KB Output is correct
7 Correct 5 ms 5352 KB Output is correct
8 Incorrect 7 ms 5352 KB Output isn't correct
9 Correct 7 ms 5352 KB Output is correct
10 Correct 7 ms 5352 KB Output is correct
11 Correct 6 ms 5352 KB Output is correct
12 Incorrect 7 ms 5352 KB Output isn't correct
13 Correct 6 ms 5352 KB Output is correct
14 Incorrect 8 ms 5352 KB Output isn't correct
15 Correct 7 ms 5352 KB Output is correct
16 Incorrect 10 ms 5352 KB Output isn't correct
17 Incorrect 6 ms 5352 KB Output isn't correct
18 Incorrect 9 ms 5352 KB Output isn't correct
19 Correct 7 ms 5352 KB Output is correct
20 Correct 6 ms 5352 KB Output is correct
21 Correct 7 ms 5352 KB Output is correct
22 Correct 6 ms 5352 KB Output is correct
23 Correct 7 ms 5352 KB Output is correct
24 Incorrect 9 ms 5352 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6900 KB Output is correct
2 Incorrect 112 ms 7660 KB Output isn't correct
3 Correct 73 ms 7660 KB Output is correct
4 Incorrect 143 ms 7720 KB Output isn't correct
5 Correct 62 ms 7720 KB Output is correct
6 Correct 49 ms 7720 KB Output is correct
7 Correct 106 ms 7720 KB Output is correct
8 Correct 94 ms 7720 KB Output is correct
9 Incorrect 159 ms 7720 KB Output isn't correct
10 Correct 475 ms 11968 KB Output is correct
11 Incorrect 224 ms 11968 KB Output isn't correct
12 Correct 306 ms 11968 KB Output is correct
13 Incorrect 243 ms 11968 KB Output isn't correct
14 Correct 128 ms 11968 KB Output is correct
15 Correct 225 ms 11968 KB Output is correct
16 Correct 186 ms 11968 KB Output is correct
17 Correct 164 ms 11968 KB Output is correct
18 Incorrect 182 ms 11968 KB Output isn't correct
19 Correct 301 ms 11968 KB Output is correct
20 Incorrect 688 ms 13548 KB Output isn't correct
21 Incorrect 268 ms 13548 KB Output isn't correct
22 Correct 431 ms 13548 KB Output is correct
23 Correct 458 ms 13548 KB Output is correct
24 Correct 458 ms 13548 KB Output is correct
25 Incorrect 387 ms 13548 KB Output isn't correct
26 Correct 375 ms 13548 KB Output is correct
27 Correct 352 ms 13548 KB Output is correct
28 Correct 536 ms 13548 KB Output is correct
29 Correct 374 ms 13548 KB Output is correct
30 Incorrect 704 ms 14332 KB Output isn't correct
31 Incorrect 424 ms 14332 KB Output isn't correct
32 Correct 442 ms 14332 KB Output is correct
33 Correct 292 ms 14332 KB Output is correct
34 Incorrect 611 ms 14332 KB Output isn't correct
35 Incorrect 512 ms 14332 KB Output isn't correct
36 Incorrect 301 ms 14332 KB Output isn't correct
37 Correct 394 ms 14332 KB Output is correct
38 Correct 369 ms 14332 KB Output is correct
39 Correct 706 ms 14332 KB Output is correct
40 Incorrect 549 ms 14400 KB Output isn't correct
41 Correct 907 ms 16620 KB Output is correct