oj.uz

Submission #613960

# Submission time Handle Problem Language Result Execution time Memory
613960 2022-07-30T14:41:06 Z andrei_boaca 007 (CEOI14_007) C++14
20 / 100
 223 ms 17636 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]>=dist[1][s])
            {
                if(dist[2][i]+1>=dist[2][s])
                    good=1;
            }
            if(dist[2][i]>=dist[2][s])
            {
                if(dist[1][i]+1>=dist[1][s])
                    good=1;
            }
            if(dist[1][i]==dist[2][i]&&dist[1][s]==dist[2][s]&&dist[1][i]+1>=dist[1][s]&&dist[2][i]+1>=dist[2][s])
                good=1;
        }
        if(!good)
            minim=min(minim,dist[3][i]-2);
    }
    minim--;
    cout<<max(-1,minim);
    return 0;
}

Subtask #1
6.0 / 30.0

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

Subtask #2
14.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 19 ms 6944 KB Partially correct
2 Correct 24 ms 7732 KB Output is correct
3 Partially correct 21 ms 6996 KB Partially correct
4 Correct 25 ms 7920 KB Output is correct
5 Partially correct 20 ms 6864 KB Partially correct
6 Partially correct 20 ms 7124 KB Partially correct
7 Partially correct 25 ms 7356 KB Partially correct
8 Partially correct 33 ms 7256 KB Partially correct
9 Correct 36 ms 7788 KB Output is correct
10 Partially correct 121 ms 12096 KB Partially correct
11 Correct 48 ms 9232 KB Output is correct
12 Partially correct 62 ms 10304 KB Partially correct
13 Correct 60 ms 9616 KB Output is correct
14 Correct 42 ms 8908 KB Output is correct
15 Partially correct 63 ms 10476 KB Partially correct
16 Partially correct 63 ms 10748 KB Partially correct
17 Partially correct 60 ms 10152 KB Partially correct
18 Correct 64 ms 10168 KB Output is correct
19 Partially correct 94 ms 11376 KB Partially correct
20 Correct 152 ms 14144 KB Output is correct
21 Correct 89 ms 12484 KB Output is correct
22 Partially correct 86 ms 11560 KB Partially correct
23 Incorrect 103 ms 12392 KB Output isn't correct
24 Partially correct 82 ms 12396 KB Partially correct
25 Correct 81 ms 12008 KB Output is correct
26 Incorrect 82 ms 11748 KB Output isn't correct
27 Partially correct 130 ms 12556 KB Partially correct
28 Partially correct 100 ms 12492 KB Partially correct
29 Partially correct 113 ms 13008 KB Partially correct
30 Correct 156 ms 14972 KB Output is correct
31 Correct 148 ms 13672 KB Output is correct
32 Partially correct 99 ms 12388 KB Partially correct
33 Incorrect 107 ms 12668 KB Output isn't correct
34 Correct 140 ms 13072 KB Output is correct
35 Correct 99 ms 12812 KB Output is correct
36 Correct 93 ms 13104 KB Output is correct
37 Partially correct 130 ms 14176 KB Partially correct
38 Partially correct 152 ms 13912 KB Partially correct
39 Partially correct 153 ms 13984 KB Partially correct
40 Correct 166 ms 15480 KB Output is correct
41 Partially correct 223 ms 17636 KB Partially correct