Submission #958514

#	Time	Username	Problem	Language	Result	Execution time	Memory
958514		Ghetto	007 (CEOI14_007)	C++17	100 / 100	396 ms	28368 KiB

007

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 2e5 + 5, INF = 1e9;

int n, m;
int a, b, tar1, tar2;
vector<int> adj[MAX_N];

int dist[MAX_N];
bool seen[MAX_N];
queue<int> order;
void bfs(int s) {
    for (int i = 1; i <= n; i++) seen[i] = false;

    seen[s] = true;
    dist[s] = 0;
    order.push(s);
    while (order.size()) {
        int u = order.front(); 
        order.pop();

        for (int v : adj[u]) {
            if (seen[v]) continue;
            seen[v] = true;
            dist[v] = dist[u] + 1;
            order.push(v);
        }
    }
}

int d[MAX_N][3];
int dp[MAX_N];
vector<pii> order2;
void precomp() {
    bfs(tar1);
    for (int i = 1; i <= n; i++) d[i][1] = dist[i];
    bfs(tar2);
    for (int i = 1; i <= n; i++) d[i][2] = dist[i];

    for (int i = 1; i <= n; i++) {
        if (d[i][1] != d[i][2]) continue;
        order2.push_back({d[i][1], i});
    }
    sort(order2.begin(), order2.end());

    for (pii el : order2) {
        int u = el.second;
        dp[u] = 1;
        for (int v : adj[u]) {
            if (!(d[v][1] == d[u][1] - 1 && d[v][2] == d[u][2] - 1)) continue;
            dp[u] = max(dp[u], dp[v] + 1);
        }
    }

    for (int i = 1; i <= n; i++) {
        // cout << i << ": " << d[i][1] << " " << d[i][2] << endl;
        // cout << i << ": " << dp[i] << endl;
    }
}

bool does_b_win(int new_b) {
    if (d[a][1] > d[new_b][1] || d[a][2] > d[new_b][2]) return true;
    if (d[a][1] == d[new_b][1] && d[a][2] == d[new_b][2] && d[a][1] == d[a][2] && dp[a] < dp[new_b]) return true;
    return false;
}

int main() {
    // freopen("007.in", "r", stdin);

    cin >> n >> m;
    cin >> a >> b >> tar1 >> tar2;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    precomp();

    bfs(b);
    int ans = INF;
    for (int i = 1; i <= n; i++) {
        if (!does_b_win(i)) continue;
        ans = min(ans, dist[i]);
    }
    ans--;
    cout << ans << '\n';
}

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