oj.uz

Submission #58239

# Submission time Handle Problem Language Result Execution time Memory
58239 2018-07-17T08:45:45 Z evpipis 007 (CEOI14_007) C++14
0 / 100
 996 ms 16508 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);
    return (tim[t1]+x <= dis[t1] && tim[t2]+x <= dis[t2]);
}

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: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:68:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < adj[u].size(); j++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:52: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:55: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 7 ms 5096 KB Output is correct
3 Correct 6 ms 5096 KB Output is correct
4 Incorrect 7 ms 5096 KB Output isn't correct
5 Incorrect 6 ms 5196 KB Output isn't correct
6 Partially correct 6 ms 5196 KB Partially correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 7 ms 5196 KB Output is correct
9 Correct 7 ms 5280 KB Output is correct
10 Correct 9 ms 5280 KB Output is correct
11 Correct 7 ms 5280 KB Output is correct
12 Incorrect 7 ms 5280 KB Output isn't correct
13 Correct 7 ms 5280 KB Output is correct
14 Incorrect 8 ms 5280 KB Output isn't correct
15 Correct 7 ms 5280 KB Output is correct
16 Incorrect 7 ms 5280 KB Output isn't correct
17 Incorrect 8 ms 5280 KB Output isn't correct
18 Incorrect 8 ms 5280 KB Output isn't correct
19 Correct 8 ms 5356 KB Output is correct
20 Correct 9 ms 5356 KB Output is correct
21 Correct 9 ms 5356 KB Output is correct
22 Correct 7 ms 5356 KB Output is correct
23 Correct 8 ms 5356 KB Output is correct
24 Correct 8 ms 5356 KB Output is correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6908 KB Output is correct
2 Incorrect 81 ms 7676 KB Output isn't correct
3 Correct 60 ms 7676 KB Output is correct
4 Incorrect 80 ms 7676 KB Output isn't correct
5 Correct 57 ms 7676 KB Output is correct
6 Correct 70 ms 7676 KB Output is correct
7 Correct 76 ms 7676 KB Output is correct
8 Correct 67 ms 7676 KB Output is correct
9 Incorrect 151 ms 7676 KB Output isn't correct
10 Incorrect 395 ms 12056 KB Output isn't correct
11 Incorrect 198 ms 12056 KB Output isn't correct
12 Correct 300 ms 12056 KB Output is correct
13 Incorrect 244 ms 12056 KB Output isn't correct
14 Correct 176 ms 12056 KB Output is correct
15 Correct 265 ms 12056 KB Output is correct
16 Correct 264 ms 12056 KB Output is correct
17 Correct 310 ms 12056 KB Output is correct
18 Incorrect 230 ms 12056 KB Output isn't correct
19 Incorrect 365 ms 12056 KB Output isn't correct
20 Incorrect 547 ms 13820 KB Output isn't correct
21 Incorrect 344 ms 13820 KB Output isn't correct
22 Correct 426 ms 13820 KB Output is correct
23 Correct 320 ms 13820 KB Output is correct
24 Correct 376 ms 13820 KB Output is correct
25 Incorrect 354 ms 13820 KB Output isn't correct
26 Correct 375 ms 13820 KB Output is correct
27 Correct 442 ms 13820 KB Output is correct
28 Correct 626 ms 13820 KB Output is correct
29 Incorrect 558 ms 13820 KB Output isn't correct
30 Incorrect 479 ms 14204 KB Output isn't correct
31 Incorrect 457 ms 14204 KB Output isn't correct
32 Correct 475 ms 14204 KB Output is correct
33 Correct 572 ms 14204 KB Output is correct
34 Incorrect 756 ms 14204 KB Output isn't correct
35 Incorrect 405 ms 14204 KB Output isn't correct
36 Incorrect 520 ms 14204 KB Output isn't correct
37 Correct 475 ms 14204 KB Output is correct
38 Correct 464 ms 14204 KB Output is correct
39 Correct 733 ms 14204 KB Output is correct
40 Incorrect 681 ms 14448 KB Output isn't correct
41 Partially correct 996 ms 16508 KB Partially correct