oj.uz

답안 #613880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613880 2022-07-30T12:19:58 Z andrei_boaca 007 (CEOI14_007) C++14
30 / 100
 279 ms 17528 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[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(!good)
            minim=min(minim,dist[3][i]-2);
    }
    cout<<max(-1,minim);
    return 0;
}

Subtask #1
9.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Partially correct 3 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 2 ms 4948 KB Partially correct
8 Correct 3 ms 4948 KB Output is correct
9 Partially correct 3 ms 4948 KB Partially correct
10 Correct 3 ms 4944 KB Output is correct
11 Correct 3 ms 4948 KB Output is 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 Correct 4 ms 4948 KB Output is correct
16 Correct 3 ms 4980 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Partially correct 3 ms 5076 KB Partially correct
20 Partially correct 3 ms 5076 KB Partially correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 5 ms 5076 KB Output is correct

Subtask #2
21.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 19 ms 6868 KB Partially correct
2 Correct 33 ms 7764 KB Output is correct
3 Partially correct 22 ms 7048 KB Partially correct
4 Correct 37 ms 7832 KB Output is correct
5 Correct 26 ms 6808 KB Output is correct
6 Correct 21 ms 7056 KB Output is correct
7 Correct 25 ms 7292 KB Output is correct
8 Correct 25 ms 7252 KB Output is correct
9 Correct 43 ms 7772 KB Output is correct
10 Partially correct 121 ms 12152 KB Partially correct
11 Correct 47 ms 9228 KB Output is correct
12 Partially correct 90 ms 10236 KB Partially correct
13 Correct 58 ms 9596 KB Output is correct
14 Correct 50 ms 8832 KB Output is correct
15 Partially correct 68 ms 10400 KB Partially correct
16 Correct 71 ms 10736 KB Output is correct
17 Correct 57 ms 10108 KB Output is correct
18 Correct 69 ms 10152 KB Output is correct
19 Partially correct 129 ms 11348 KB Partially correct
20 Correct 177 ms 14144 KB Output is correct
21 Correct 120 ms 12592 KB Output is correct
22 Partially correct 91 ms 11556 KB Partially correct
23 Partially correct 120 ms 12448 KB Partially correct
24 Partially correct 107 ms 12400 KB Partially correct
25 Correct 93 ms 12052 KB Output is correct
26 Partially correct 74 ms 11604 KB Partially correct
27 Correct 100 ms 12456 KB Output is correct
28 Correct 116 ms 12568 KB Output is correct
29 Partially correct 120 ms 12940 KB Partially correct
30 Correct 177 ms 15020 KB Output is correct
31 Correct 153 ms 13696 KB Output is correct
32 Partially correct 105 ms 12392 KB Partially correct
33 Partially correct 108 ms 12748 KB Partially correct
34 Correct 127 ms 12992 KB Output is correct
35 Correct 101 ms 12744 KB Output is correct
36 Correct 109 ms 13060 KB Output is correct
37 Correct 140 ms 14052 KB Output is correct
38 Correct 143 ms 13852 KB Output is correct
39 Correct 133 ms 13884 KB Output is correct
40 Correct 189 ms 15508 KB Output is correct
41 Partially correct 279 ms 17528 KB Partially correct