oj.uz

Submission #58244

# Submission time Handle Problem Language Result Execution time Memory
58244 2018-07-17T08:53:02 Z evpipis 007 (CEOI14_007) C++14
0 / 100
 915 ms 16584 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] == -1 && dis[t2] == -1);
    if (dis[t1]+1 < tim[t1]+x || dis[t2]+1 < tim[t2]+x)
        return false;
    return true;
    //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:71:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < adj[u].size(); j++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:55: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:58: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 Incorrect 8 ms 5112 KB Output isn't correct
2 Incorrect 8 ms 5120 KB Output isn't correct
3 Incorrect 7 ms 5192 KB Output isn't correct
4 Incorrect 7 ms 5192 KB Output isn't correct
5 Incorrect 8 ms 5192 KB Output isn't correct
6 Incorrect 8 ms 5192 KB Output isn't correct
7 Incorrect 7 ms 5236 KB Output isn't correct
8 Incorrect 8 ms 5236 KB Output isn't correct
9 Incorrect 6 ms 5236 KB Output isn't correct
10 Incorrect 8 ms 5308 KB Output isn't correct
11 Incorrect 6 ms 5308 KB Output isn't correct
12 Incorrect 6 ms 5308 KB Output isn't correct
13 Incorrect 7 ms 5308 KB Output isn't correct
14 Incorrect 7 ms 5308 KB Output isn't correct
15 Incorrect 8 ms 5308 KB Output isn't correct
16 Incorrect 8 ms 5308 KB Output isn't correct
17 Incorrect 7 ms 5308 KB Output isn't correct
18 Incorrect 8 ms 5308 KB Output isn't correct
19 Incorrect 7 ms 5308 KB Output isn't correct
20 Incorrect 8 ms 5308 KB Output isn't correct
21 Incorrect 9 ms 5308 KB Output isn't correct
22 Incorrect 8 ms 5308 KB Output isn't correct
23 Incorrect 8 ms 5308 KB Output isn't correct
24 Incorrect 7 ms 5356 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 6892 KB Output isn't correct
2 Incorrect 106 ms 7740 KB Output isn't correct
3 Incorrect 58 ms 7740 KB Output isn't correct
4 Incorrect 74 ms 7740 KB Output isn't correct
5 Incorrect 64 ms 7740 KB Output isn't correct
6 Incorrect 55 ms 7740 KB Output isn't correct
7 Incorrect 96 ms 7740 KB Output isn't correct
8 Incorrect 105 ms 7740 KB Output isn't correct
9 Incorrect 156 ms 7740 KB Output isn't correct
10 Incorrect 569 ms 11924 KB Output isn't correct
11 Incorrect 212 ms 11924 KB Output isn't correct
12 Incorrect 308 ms 11924 KB Output isn't correct
13 Incorrect 239 ms 11924 KB Output isn't correct
14 Correct 180 ms 11924 KB Output is correct
15 Incorrect 266 ms 11924 KB Output isn't correct
16 Incorrect 237 ms 11924 KB Output isn't correct
17 Incorrect 311 ms 11924 KB Output isn't correct
18 Incorrect 381 ms 11924 KB Output isn't correct
19 Incorrect 309 ms 11924 KB Output isn't correct
20 Incorrect 541 ms 13516 KB Output isn't correct
21 Incorrect 427 ms 13516 KB Output isn't correct
22 Incorrect 433 ms 13516 KB Output isn't correct
23 Incorrect 411 ms 13516 KB Output isn't correct
24 Incorrect 535 ms 13516 KB Output isn't correct
25 Incorrect 532 ms 13516 KB Output isn't correct
26 Incorrect 346 ms 13516 KB Output isn't correct
27 Incorrect 439 ms 13516 KB Output isn't correct
28 Incorrect 801 ms 13516 KB Output isn't correct
29 Incorrect 626 ms 13516 KB Output isn't correct
30 Incorrect 553 ms 14332 KB Output isn't correct
31 Incorrect 474 ms 14332 KB Output isn't correct
32 Incorrect 611 ms 14332 KB Output isn't correct
33 Incorrect 489 ms 14332 KB Output isn't correct
34 Incorrect 603 ms 14332 KB Output isn't correct
35 Incorrect 379 ms 14332 KB Output isn't correct
36 Incorrect 482 ms 14332 KB Output isn't correct
37 Incorrect 690 ms 14332 KB Output isn't correct
38 Incorrect 613 ms 14332 KB Output isn't correct
39 Incorrect 915 ms 14332 KB Output isn't correct
40 Incorrect 697 ms 14460 KB Output isn't correct
41 Incorrect 859 ms 16584 KB Output isn't correct