Submission #556521

#	Time	Username	Problem	Language	Result	Execution time	Memory
556521		alextodoran	007 (CEOI14_007)	C++17	30 / 100	1097 ms	16116 KiB

007

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

int N, M;

int me, him, sv1, sv2;

vector <int> adj[N_MAX + 2];

void bfs (int start, int dist[]) {
    fill(dist + 1, dist + N + 1, INT_MAX);
    queue <int> q;
    dist[start] = 0;
    q.push(start);
    while (q.empty() == false) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == INT_MAX) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

int dist1[N_MAX + 2];
int dist2[N_MAX + 2];

int dfs (int u) {
    int ret = 0;
    for (int v : adj[u]) {
        if (dist1[u] > dist1[v] && dist2[u] > dist2[v]) {
            ret = max(ret, dfs(v) + 1);
        }
    }
    return ret;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    cin >> me >> him >> sv1 >> sv2;
    for (int i = 1; i <= M; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bfs(sv1, dist1);
    bfs(sv2, dist2);

    int wait1 = dist1[him] - dist1[me];
    int wait2 = dist2[him] - dist2[me];
    int wait;
    if (wait1 != wait2) {
        wait = min(wait1, wait2);
    } else {
        int decme = dfs(me);
        int dechim = dfs(him);
        if (wait1 + decme >= dechim) {
            wait = wait1;
        } else {
            wait = wait1 - 1;
        }
    }
    cout << (wait >= 0 ? wait : -1) << "\n";

    return 0;
}

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