제출 #118457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
118457		minhtung0404	007 (CEOI14_007)	C++17	100 / 100	303 ms	25208 KiB

007

//https://oj.uz/problem/view/CEOI14_007

#include<bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;

vector <int> G[N];
int n, m, p[2], a[2];
int d[2][N], d2[N], Max[N];
bool ck[N];

void bfs(int u, int t){
    queue <int> mq; mq.push(u); d[t][u] = 1;
    while (mq.size()){
        u = mq.front(); mq.pop();
        for (auto v : G[u]){
            if (!d[t][v]){
                d[t][v] = d[t][u] + 1;
                mq.push(v);
            }
        }
    }
}

void dfs(int u){
    Max[u] = 1;
    for (auto v : G[u]){
        if (d[0][v] + 1 == d[0][u] && d[1][v] + 1 == d[1][u]){
            if (!Max[v]) dfs(v);
            Max[u] = max(Max[u], Max[v] + 1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    cin >> p[0] >> p[1] >> a[0] >> a[1];
    while (m--){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(a[0], 0); bfs(a[1], 1);
    for (int i = 1; i <= n; i++){
        if (d[0][i] < d[0][p[0]] || d[1][i] < d[1][p[0]]) ck[i] = true;
    }
    if (d[0][p[0]] == d[1][p[0]]){
        for (int i = 1; i <= n; i++){
            if (d[0][i] == d[1][i] && d[0][i] == d[0][p[0]] && !Max[i]) dfs(i);
        }
        for (int i = 1; i <= n; i++) if (Max[i] > Max[p[0]]) ck[i] = true;
    }
    queue <int> mq; mq.push(p[1]); d2[p[1]] = 1;
    while (mq.size()){
        int u = mq.front(); mq.pop();
        if (ck[u]) return cout << d2[u] - 2, 0;
        for (auto v : G[u]){
            if (!d2[v]){
                d2[v] = d2[u] + 1;
                mq.push(v);
            }
        }
    }
}
/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
*/

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70