Submission #391819

#	Time	Username	Problem	Language	Result	Execution time	Memory
391819		abc864197532	007 (CEOI14_007)	C++17	0 / 100	266 ms	21320 KiB

007

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define pll pair<lli,lli>
#define X first
#define Y second
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) { \
    for (auto a : x) cout << a << endl; \
    cout << endl;\
}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 300000, abc = 864197532, Doludu = 123;

vector <int> adj[N];
int dist[N], disa[N], disb[N], s, t, a, b, n;

bool chk(int d) {
    int mna = 1 << 30, mnb = 1 << 30;
    for (int i = 0; i < n; ++i) if (dist[i] <= d) mna = min(mna, disa[i]), mnb = min(mnb, disb[i]);
    if (mna < disa[s]) return false;
    if (mnb < disb[s]) return false;
    return true;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m;
    cin >> n >> m >> s >> t >> a >> b, --s, --t, --a, --b;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v, --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for (int i = 0; i < n; ++i) dist[i] = -1;
    dist[t] = 0;
    queue <int> q;
    q.push(t);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) if (dist[u] == -1) {
            dist[u] = dist[v] + 1;
            q.push(u);
        }
    }
    for (int i = 0; i < n; ++i) disa[i] = -1;
    disa[a] = 0;
    q.push(a);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) if (disa[u] == -1) {
            disa[u] = disa[v] + 1;
            q.push(u);
        }
    }
    for (int i = 0; i < n; ++i) disb[i] = -1;
    disb[b] = 0;
    q.push(b);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) if (disb[u] == -1) {
            disb[u] = disb[v] + 1;
            q.push(u);
        }
    }
    if (!chk(0)) {
        cout << -1 << endl;
    } else {
        int l = 0, r = n + 1;
        while (r - l > 1) {
            int mid = l + r >> 1;
            if (chk(mid)) l = mid;
            else r = mid;
        }
        cout << l << endl;
    }
}

Compilation message (stderr)

007.cpp: In function 'int main()':
007.cpp:77:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |             int mid = l + r >> 1;
      |                       ~~^~~

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