제출 #391823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391823		syl123456	007 (CEOI14_007)	C++17	44 / 100	267 ms	18296 KiB

007

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
typedef long long ll;
typedef pair<int, int> pi;
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, s, d, a, b;
    cin >> n >> m >> s >> d >> a >> b;
    --s, --d, --a, --b;
    vector<int> g[n];
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].push_back(y), g[y].push_back(x);
    }
    vector<int> disd(n, -1), diss(n, -1), disa(n, -1), disb(n, -1);
    queue<int> q;
    disd[d] = 0, q.push(d);
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (int j : g[i]) if (disd[j] == -1)
                disd[j] = disd[i] + 1, q.push(j);
    }
    diss[s] = 0, q.push(s);
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (int j : g[i]) if (diss[j] == -1)
                diss[j] = diss[i] + 1, q.push(j);
    }
    if (disd[a] != disd[b]) {
        if (disd[a] < disd[b]) cout << max(disd[a] - diss[a], -1);
        else cout << max(disd[b] - diss[b], -1);
    }
    else {
        int tmp = max(disd[a] - 1 - diss[a], disd[b] - 1 - diss[b]);
        vector<int> disa(n, -1), disb(n, -1);
        disa[a] = 0, q.push(a);
        while (!q.empty()) {
            int i = q.front();
            q.pop();
            for (int j : g[i]) if (disa[j] == -1)
                disa[j] = disa[i] + 1, q.push(j);
        }
        disb[b] = 0, q.push(b);
        while (!q.empty()) {
            int i = q.front();
            q.pop();
            for (int j : g[i]) if (disb[j] == -1)
                disb[j] = disb[i] + 1, q.push(j);
        }
        int x = d;
        for (int i = 0; i < n; ++i)
            if (disa[i] == disb[i] && disd[i] + disa[i] == disd[a] && disa[i] < disa[x])
                x = i;
        for (int i = 0; i < n; ++i) if (disa[i] <= disa[x] && disb[i] <= disb[x])
            tmp = max(tmp, disd[x] - diss[i]);
        cout << max(tmp, -1);
    }
}

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