oj.uz

Submission #58236

# Submission time Handle Problem Language Result Execution time Memory
58236 2018-07-17T08:42:56 Z evpipis 007 (CEOI14_007) C++14
0 / 100
 1000 ms 50036 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;
}

/*
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: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 Partially correct 7 ms 4984 KB Partially correct
2 Incorrect 8 ms 5100 KB Output isn't correct
3 Partially correct 8 ms 5284 KB Partially correct
4 Partially correct 7 ms 5284 KB Partially correct
5 Partially correct 7 ms 5284 KB Partially correct
6 Incorrect 7 ms 5284 KB Output isn't correct
7 Incorrect 9 ms 5296 KB Output isn't correct
8 Incorrect 8 ms 5296 KB Output isn't correct
9 Incorrect 9 ms 5296 KB Output isn't correct
10 Incorrect 7 ms 5312 KB Output isn't correct
11 Incorrect 7 ms 5316 KB Output isn't correct
12 Incorrect 7 ms 5316 KB Output isn't correct
13 Incorrect 8 ms 5316 KB Output isn't correct
14 Incorrect 8 ms 5316 KB Output isn't correct
15 Incorrect 7 ms 5316 KB Output isn't correct
16 Partially correct 8 ms 5316 KB Partially correct
17 Incorrect 8 ms 5316 KB Output isn't correct
18 Incorrect 9 ms 5316 KB Output isn't correct
19 Incorrect 9 ms 5316 KB Output isn't correct
20 Incorrect 9 ms 5316 KB Output isn't correct
21 Incorrect 8 ms 5316 KB Output isn't correct
22 Incorrect 8 ms 5316 KB Output isn't correct
23 Incorrect 8 ms 5332 KB Output isn't correct
24 Incorrect 8 ms 5344 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 7384 KB Output isn't correct
2 Incorrect 107 ms 8988 KB Output isn't correct
3 Incorrect 90 ms 8988 KB Output isn't correct
4 Incorrect 129 ms 10240 KB Output isn't correct
5 Incorrect 64 ms 10240 KB Output isn't correct
6 Incorrect 67 ms 10536 KB Output isn't correct
7 Incorrect 106 ms 11300 KB Output isn't correct
8 Incorrect 72 ms 11860 KB Output isn't correct
9 Incorrect 129 ms 13324 KB Output isn't correct
10 Incorrect 522 ms 22768 KB Output isn't correct
11 Incorrect 235 ms 22768 KB Output isn't correct
12 Incorrect 314 ms 23028 KB Output isn't correct
13 Incorrect 206 ms 23728 KB Output isn't correct
14 Correct 134 ms 24124 KB Output is correct
15 Incorrect 337 ms 26776 KB Output isn't correct
16 Incorrect 299 ms 28560 KB Output isn't correct
17 Incorrect 275 ms 29276 KB Output isn't correct
18 Incorrect 224 ms 30556 KB Output isn't correct
19 Incorrect 328 ms 34484 KB Output isn't correct
20 Incorrect 545 ms 42652 KB Output isn't correct
21 Incorrect 409 ms 42652 KB Output isn't correct
22 Incorrect 437 ms 43424 KB Output isn't correct
23 Incorrect 339 ms 44892 KB Output isn't correct
24 Incorrect 344 ms 44892 KB Output isn't correct
25 Incorrect 349 ms 44892 KB Output isn't correct
26 Incorrect 246 ms 44892 KB Output isn't correct
27 Incorrect 383 ms 44924 KB Output isn't correct
28 Incorrect 576 ms 45052 KB Output isn't correct
29 Incorrect 475 ms 45720 KB Output isn't correct
30 Incorrect 767 ms 47612 KB Output isn't correct
31 Incorrect 640 ms 47612 KB Output isn't correct
32 Incorrect 620 ms 47612 KB Output isn't correct
33 Incorrect 430 ms 47612 KB Output isn't correct
34 Incorrect 553 ms 47612 KB Output isn't correct
35 Incorrect 484 ms 47612 KB Output isn't correct
36 Incorrect 575 ms 47612 KB Output isn't correct
37 Incorrect 737 ms 47612 KB Output isn't correct
38 Incorrect 720 ms 47612 KB Output isn't correct
39 Incorrect 958 ms 47612 KB Output isn't correct
40 Incorrect 714 ms 47856 KB Output isn't correct
41 Execution timed out 1064 ms 50036 KB Time limit exceeded