oj.uz

답안 #105822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105822 2019-04-15T07:58:24 Z Bodo171 007 (CEOI14_007) C++14
93 / 100
 668 ms 18404 KB 
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
int d[4][nmax];
int q[nmax];
int p,u,i,j,s,t,a,b,n,m,x,y,det_s,det_t,ans;
void bfs(int x,int wh)
{
    q[u=1]=x;d[wh][x]=1;
    for(p=1;p<=u;p++)
    {
        x=q[p];
        for(i=0;i<v[x].size();i++)
            if(!d[wh][v[x][i]])
        {
            d[wh][v[x][i]]=d[wh][x]+1;
            q[++u]=v[x][i];
        }
    }
}
int main()
{
   // freopen("data.in","r",stdin);
    cin>>n>>m;
    cin>>s>>t>>a>>b;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bfs(s,0);
    bfs(t,1);
    bfs(a,2);
    bfs(b,3);
    det_s=n+1;det_t=n+1;
    for(i=1;i<=n;i++)
    {
        if(d[0][i]+d[2][i]-1==d[0][a]&&d[0][i]+d[3][i]-1==d[0][b])
            det_s=min(det_s,d[2][i]);
        if(d[1][i]+d[2][i]-1==d[1][a]&&d[1][i]+d[3][i]-1==d[1][b])
            det_t=min(det_t,d[2][i]);
    }
    ans=min(d[1][a]-d[0][a]-(d[0][a]==d[0][b]&&det_s>det_t),d[1][b]-d[0][b]-(d[0][b]==d[0][a]&&det_s>det_t));
    if(ans<0) ans=-1;
    cout<<ans;
    return 0;
}

Compilation message

007.cpp: In function 'void bfs(int, int)':
007.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

Subtask #1
23.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 19 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Partially correct 6 ms 5120 KB Partially correct
12 Correct 6 ms 4992 KB Output is correct
13 Correct 7 ms 5120 KB Output is correct
14 Correct 7 ms 5120 KB Output is correct
15 Correct 7 ms 4992 KB Output is correct
16 Correct 7 ms 5120 KB Output is correct
17 Correct 7 ms 5120 KB Output is correct
18 Correct 9 ms 5092 KB Output is correct
19 Correct 7 ms 5120 KB Output is correct
20 Correct 7 ms 5120 KB Output is correct
21 Correct 7 ms 5120 KB Output is correct
22 Correct 8 ms 5120 KB Output is correct
23 Correct 7 ms 5120 KB Output is correct
24 Correct 7 ms 5120 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 7060 KB Output is correct
2 Correct 70 ms 8056 KB Output is correct
3 Correct 63 ms 7172 KB Output is correct
4 Correct 76 ms 8184 KB Output is correct
5 Correct 61 ms 7000 KB Output is correct
6 Correct 51 ms 7288 KB Output is correct
7 Correct 61 ms 7544 KB Output is correct
8 Correct 62 ms 7572 KB Output is correct
9 Correct 116 ms 7928 KB Output is correct
10 Correct 486 ms 12408 KB Output is correct
11 Correct 123 ms 9628 KB Output is correct
12 Correct 170 ms 10872 KB Output is correct
13 Correct 114 ms 10028 KB Output is correct
14 Correct 95 ms 9184 KB Output is correct
15 Correct 179 ms 11128 KB Output is correct
16 Correct 145 ms 11256 KB Output is correct
17 Correct 133 ms 10516 KB Output is correct
18 Correct 173 ms 10632 KB Output is correct
19 Correct 254 ms 11768 KB Output is correct
20 Correct 447 ms 14812 KB Output is correct
21 Correct 216 ms 13176 KB Output is correct
22 Correct 188 ms 12140 KB Output is correct
23 Correct 217 ms 13176 KB Output is correct
24 Correct 207 ms 13088 KB Output is correct
25 Correct 199 ms 12660 KB Output is correct
26 Correct 184 ms 12280 KB Output is correct
27 Correct 191 ms 13220 KB Output is correct
28 Correct 234 ms 13352 KB Output is correct
29 Correct 289 ms 13672 KB Output is correct
30 Correct 575 ms 15584 KB Output is correct
31 Correct 238 ms 14468 KB Output is correct
32 Correct 237 ms 13048 KB Output is correct
33 Correct 197 ms 13432 KB Output is correct
34 Correct 248 ms 13816 KB Output is correct
35 Correct 235 ms 13540 KB Output is correct
36 Correct 228 ms 13816 KB Output is correct
37 Correct 288 ms 14960 KB Output is correct
38 Correct 285 ms 14652 KB Output is correct
39 Correct 321 ms 14780 KB Output is correct
40 Correct 412 ms 16248 KB Output is correct
41 Correct 668 ms 18404 KB Output is correct