oj.uz

Submission #58218

# Submission time Handle Problem Language Result Execution time Memory
58218 2018-07-17T08:18:00 Z evpipis 007 (CEOI14_007) C++14
0 / 100
 841 ms 102252 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;
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] = -1;

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

    return (dis[t1] == -1 && dis[t2] == -1);
}

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

Compilation message

007.cpp: In function 'bool check(int)':
007.cpp:27: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:67:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < adj[u].size(); j++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:51: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:54: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 7 ms 4984 KB Output is correct
2 Correct 8 ms 5104 KB Output is correct
3 Correct 8 ms 5344 KB Output is correct
4 Incorrect 7 ms 5344 KB Output isn't correct
5 Incorrect 9 ms 5344 KB Output isn't correct
6 Correct 7 ms 5344 KB Output is correct
7 Correct 7 ms 5344 KB Output is correct
8 Incorrect 9 ms 5368 KB Output isn't correct
9 Correct 7 ms 5368 KB Output is correct
10 Correct 9 ms 5432 KB Output is correct
11 Correct 9 ms 5432 KB Output is correct
12 Incorrect 10 ms 5432 KB Output isn't correct
13 Correct 8 ms 5456 KB Output is correct
14 Incorrect 6 ms 5456 KB Output isn't correct
15 Correct 7 ms 5456 KB Output is correct
16 Incorrect 8 ms 5536 KB Output isn't correct
17 Incorrect 9 ms 5536 KB Output isn't correct
18 Incorrect 9 ms 5540 KB Output isn't correct
19 Correct 7 ms 5588 KB Output is correct
20 Correct 8 ms 5588 KB Output is correct
21 Correct 7 ms 5588 KB Output is correct
22 Correct 7 ms 5588 KB Output is correct
23 Correct 8 ms 5588 KB Output is correct
24 Incorrect 9 ms 5652 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7832 KB Output is correct
2 Incorrect 86 ms 9096 KB Output isn't correct
3 Correct 95 ms 9096 KB Output is correct
4 Incorrect 63 ms 10292 KB Output isn't correct
5 Correct 74 ms 10292 KB Output is correct
6 Correct 53 ms 10800 KB Output is correct
7 Correct 52 ms 11564 KB Output is correct
8 Correct 60 ms 12036 KB Output is correct
9 Incorrect 112 ms 13456 KB Output isn't correct
10 Correct 277 ms 22944 KB Output is correct
11 Incorrect 214 ms 22944 KB Output isn't correct
12 Correct 272 ms 23348 KB Output is correct
13 Incorrect 168 ms 23880 KB Output isn't correct
14 Correct 164 ms 24348 KB Output is correct
15 Correct 223 ms 26928 KB Output is correct
16 Correct 325 ms 28752 KB Output is correct
17 Correct 258 ms 29468 KB Output is correct
18 Incorrect 258 ms 30712 KB Output isn't correct
19 Correct 297 ms 34496 KB Output is correct
20 Incorrect 411 ms 42920 KB Output isn't correct
21 Incorrect 228 ms 42932 KB Output isn't correct
22 Correct 217 ms 43724 KB Output is correct
23 Correct 378 ms 46400 KB Output is correct
24 Correct 195 ms 48292 KB Output is correct
25 Incorrect 295 ms 49904 KB Output isn't correct
26 Correct 364 ms 51232 KB Output is correct
27 Correct 296 ms 53984 KB Output is correct
28 Correct 589 ms 56108 KB Output is correct
29 Correct 375 ms 60028 KB Output is correct
30 Incorrect 534 ms 67832 KB Output isn't correct
31 Incorrect 325 ms 68452 KB Output isn't correct
32 Correct 318 ms 69404 KB Output is correct
33 Correct 624 ms 71700 KB Output is correct
34 Incorrect 388 ms 74228 KB Output isn't correct
35 Incorrect 233 ms 76128 KB Output isn't correct
36 Incorrect 349 ms 78528 KB Output isn't correct
37 Correct 758 ms 81996 KB Output is correct
38 Correct 343 ms 84136 KB Output is correct
39 Correct 580 ms 86528 KB Output is correct
40 Incorrect 667 ms 92548 KB Output isn't correct
41 Correct 841 ms 102252 KB Output is correct