oj.uz

답안 #613903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613903 2022-07-30T12:47:53 Z andrei_boaca 007 (CEOI14_007) C++14
30 / 100
 218 ms 17592 KB 
#include <bits/stdc++.h>

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

Subtask #1
9.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Partially correct 4 ms 4948 KB Partially correct
3 Partially correct 3 ms 4948 KB Partially correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is 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 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 5076 KB Output is correct
13 Partially correct 3 ms 5076 KB Partially correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 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 3 ms 5076 KB Partially correct
20 Partially correct 3 ms 5076 KB Partially correct
21 Correct 3 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 3 ms 5076 KB Output is correct

Subtask #2
21.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 19 ms 6860 KB Partially correct
2 Correct 27 ms 7940 KB Output is correct
3 Partially correct 26 ms 7068 KB Partially correct
4 Correct 36 ms 7924 KB Output is correct
5 Correct 26 ms 6764 KB Output is correct
6 Correct 24 ms 7116 KB Output is correct
7 Correct 23 ms 7348 KB Output is correct
8 Correct 26 ms 7252 KB Output is correct
9 Correct 32 ms 7708 KB Output is correct
10 Partially correct 114 ms 12176 KB Partially correct
11 Correct 45 ms 9264 KB Output is correct
12 Partially correct 63 ms 10368 KB Partially correct
13 Correct 53 ms 9612 KB Output is correct
14 Correct 40 ms 8796 KB Output is correct
15 Partially correct 86 ms 10428 KB Partially correct
16 Correct 68 ms 10652 KB Output is correct
17 Correct 58 ms 10156 KB Output is correct
18 Correct 60 ms 10188 KB Output is correct
19 Partially correct 90 ms 11320 KB Partially correct
20 Correct 153 ms 14140 KB Output is correct
21 Correct 119 ms 12476 KB Output is correct
22 Partially correct 100 ms 11464 KB Partially correct
23 Partially correct 89 ms 12416 KB Partially correct
24 Partially correct 91 ms 12396 KB Partially correct
25 Correct 107 ms 12044 KB Output is correct
26 Partially correct 104 ms 11540 KB Partially correct
27 Correct 94 ms 12556 KB Output is correct
28 Correct 142 ms 12456 KB Output is correct
29 Partially correct 127 ms 13000 KB Partially correct
30 Correct 212 ms 14936 KB Output is correct
31 Correct 108 ms 13596 KB Output is correct
32 Partially correct 109 ms 12364 KB Partially correct
33 Partially correct 106 ms 12732 KB Partially correct
34 Correct 131 ms 13004 KB Output is correct
35 Correct 103 ms 12724 KB Output is correct
36 Correct 108 ms 13060 KB Output is correct
37 Correct 165 ms 14064 KB Output is correct
38 Correct 133 ms 13920 KB Output is correct
39 Correct 168 ms 14084 KB Output is correct
40 Correct 216 ms 15500 KB Output is correct
41 Partially correct 218 ms 17592 KB Partially correct