oj.uz

Submission #613951

# Submission time Handle Problem Language Result Execution time Memory
613951 2022-07-30T14:22:04 Z andrei_boaca 007 (CEOI14_007) C++14
0 / 100
 219 ms 17644 KB 
#include <bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
typedef long long ll;
int n,m,s,d,a,b;
vector<int> muchii[200005];
int dist[5][200005];
void bfs(int start,int index)
{
    for(int i=1;i<=n;i++)
        dist[index][i]=1e9;
    dist[index][start]=0;
    queue<int> coada;
    coada.push(start);
    while(!coada.empty())
    {
        int nod=coada.front();
        coada.pop();
        for(int i:muchii[nod])
            if(dist[index][i]>dist[index][nod]+1)
            {
                dist[index][i]=dist[index][nod]+1;
                coada.push(i);
            }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>s>>d>>a>>b;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }
    bfs(a,1);
    bfs(b,2);
    bfs(d,3);
    bfs(s,4);
    int minim=1e9;
    for(int i=1;i<=n;i++)
    {
        bool good;
        if(dist[4][i]<=1)
            good=1;
        else
        {
            good=0;
            if(dist[1][i]+rng()%2>=dist[1][s])
            {
                if(dist[2][i]+1>=dist[2][s])
                    good=1;
            }
            if(dist[2][i]+rng()%2>=dist[2][s])
            {
                if(dist[1][i]+1>=dist[1][s])
                    good=1;
            }
        }
        if(!good)
            minim=min(minim,dist[3][i]-2);
    }
    cout<<max(-1,minim);
    return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:53:34: warning: comparison of integer expressions of different signedness: 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |             if(dist[1][i]+rng()%2>=dist[1][s])
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
007.cpp:58:34: warning: comparison of integer expressions of different signedness: 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |             if(dist[2][i]+rng()%2>=dist[2][s])
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Partially correct 3 ms 5008 KB Partially correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Incorrect 3 ms 5056 KB Output isn't correct
6 Correct 3 ms 5000 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4960 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 5076 KB Output is correct
14 Incorrect 3 ms 4948 KB Output isn't correct
15 Correct 3 ms 4948 KB Output is correct
16 Incorrect 3 ms 5076 KB Output isn't correct
17 Incorrect 3 ms 5076 KB Output isn't correct
18 Correct 3 ms 5076 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 3 ms 5004 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 3 ms 5076 KB Output is correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 21 ms 6948 KB Partially correct
2 Correct 30 ms 7768 KB Output is correct
3 Partially correct 31 ms 6956 KB Partially correct
4 Incorrect 27 ms 7836 KB Output isn't correct
5 Correct 25 ms 6796 KB Output is correct
6 Correct 20 ms 7116 KB Output is correct
7 Correct 24 ms 7332 KB Output is correct
8 Correct 25 ms 7224 KB Output is correct
9 Correct 33 ms 7764 KB Output is correct
10 Partially correct 119 ms 12080 KB Partially correct
11 Incorrect 45 ms 9268 KB Output isn't correct
12 Partially correct 71 ms 10304 KB Partially correct
13 Incorrect 51 ms 9528 KB Output isn't correct
14 Correct 40 ms 8872 KB Output is correct
15 Partially correct 60 ms 10444 KB Partially correct
16 Correct 70 ms 10720 KB Output is correct
17 Correct 62 ms 10148 KB Output is correct
18 Incorrect 64 ms 10104 KB Output isn't correct
19 Partially correct 86 ms 11368 KB Partially correct
20 Correct 158 ms 14196 KB Output is correct
21 Incorrect 89 ms 12476 KB Output isn't correct
22 Correct 81 ms 11452 KB Output is correct
23 Partially correct 85 ms 12408 KB Partially correct
24 Correct 83 ms 12340 KB Output is correct
25 Correct 89 ms 11940 KB Output is correct
26 Correct 78 ms 11528 KB Output is correct
27 Correct 93 ms 12544 KB Output is correct
28 Correct 109 ms 12504 KB Output is correct
29 Partially correct 111 ms 13008 KB Partially correct
30 Correct 167 ms 15008 KB Output is correct
31 Correct 113 ms 13692 KB Output is correct
32 Partially correct 104 ms 12404 KB Partially correct
33 Partially correct 102 ms 12752 KB Partially correct
34 Correct 113 ms 13044 KB Output is correct
35 Incorrect 95 ms 12756 KB Output isn't correct
36 Incorrect 92 ms 13108 KB Output isn't correct
37 Correct 130 ms 14156 KB Output is correct
38 Correct 124 ms 13908 KB Output is correct
39 Correct 134 ms 13932 KB Output is correct
40 Correct 170 ms 15484 KB Output is correct
41 Partially correct 219 ms 17644 KB Partially correct