oj.uz

Submission #613819

# Submission time Handle Problem Language Result Execution time Memory
613819 2022-07-30T11:32:52 Z andrei_boaca 007 (CEOI14_007) C++14
30 / 100
 254 ms 17588 KB 
#include <bits/stdc++.h>

using namespace std;
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[1][i]>=dist[1][s]&&dist[2][i]>=dist[2][s])||dist[4][i]<=1)
            good=1;
        else
            good=0;
        if(!good)
            minim=min(minim,dist[3][i]-2);
    }
    cout<<max(-1,minim);
    return 0;
}

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4948 KB Partially correct
2 Partially correct 2 ms 4948 KB Partially 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 Correct 2 ms 4948 KB Output is correct
7 Partially correct 3 ms 4948 KB Partially correct
8 Correct 3 ms 4948 KB Output is correct
9 Partially correct 3 ms 4972 KB Partially correct
10 Partially correct 3 ms 4948 KB Partially correct
11 Partially correct 3 ms 4948 KB Partially correct
12 Correct 2 ms 4948 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 4948 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 5088 KB Partially correct
21 Partially correct 3 ms 5076 KB Partially correct
22 Partially correct 3 ms 5076 KB Partially correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 4 ms 5076 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 19 ms 6900 KB Partially correct
2 Correct 26 ms 7772 KB Output is correct
3 Partially correct 21 ms 7044 KB Partially correct
4 Correct 31 ms 7892 KB Output is correct
5 Partially correct 22 ms 6828 KB Partially correct
6 Partially correct 29 ms 7124 KB Partially correct
7 Partially correct 26 ms 7328 KB Partially correct
8 Partially correct 29 ms 7340 KB Partially correct
9 Correct 35 ms 7732 KB Output is correct
10 Partially correct 111 ms 12116 KB Partially correct
11 Correct 42 ms 9252 KB Output is correct
12 Partially correct 73 ms 10312 KB Partially correct
13 Correct 59 ms 9616 KB Output is correct
14 Correct 42 ms 8776 KB Output is correct
15 Partially correct 69 ms 10388 KB Partially correct
16 Partially correct 67 ms 10768 KB Partially correct
17 Partially correct 58 ms 10160 KB Partially correct
18 Correct 79 ms 10072 KB Output is correct
19 Partially correct 116 ms 11308 KB Partially correct
20 Correct 171 ms 14160 KB Output is correct
21 Correct 90 ms 12588 KB Output is correct
22 Partially correct 83 ms 11520 KB Partially correct
23 Partially correct 106 ms 12432 KB Partially correct
24 Partially correct 84 ms 12312 KB Partially correct
25 Correct 86 ms 11892 KB Output is correct
26 Partially correct 77 ms 11644 KB Partially correct
27 Partially correct 107 ms 12452 KB Partially correct
28 Partially correct 113 ms 12576 KB Partially correct
29 Partially correct 116 ms 12956 KB Partially correct
30 Correct 163 ms 14920 KB Output is correct
31 Correct 103 ms 13664 KB Output is correct
32 Partially correct 106 ms 12420 KB Partially correct
33 Partially correct 92 ms 12748 KB Partially correct
34 Correct 120 ms 13200 KB Output is correct
35 Correct 87 ms 12780 KB Output is correct
36 Correct 90 ms 13104 KB Output is correct
37 Partially correct 145 ms 14140 KB Partially correct
38 Partially correct 145 ms 13960 KB Partially correct
39 Partially correct 127 ms 13900 KB Partially correct
40 Correct 173 ms 15432 KB Output is correct
41 Partially correct 254 ms 17588 KB Partially correct