Submission #1232608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232608		nrg_studio	007 (CEOI14_007)	C++20	100 / 100	173 ms	17720 KiB

007

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<ld,ld>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int N = 2e5;
int d_007[N], d_null[N], d_a[N], d_b[N];
vec<int> adj[N];

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

    int n, m; cin >> n >> m;
    int s, d, a, b; cin >> s >> d >> a >> b;
    for (int i=0;i<m;i++) {
        int a1, b1; cin >> a1 >> b1;
        adj[--a1].pb(--b1);
        adj[b1].pb(a1);
    }
    for (int i=0;i<n;i++) {d_007[i] = d_null[i] = d_a[i] = d_b[i] = INT_MAX;}
    auto bfs = [&](int* dist, int src) {
        queue<int> q;
        q.push(src); dist[src] = 0;
        while (q.size()) {
            int cur = q.front(); q.pop();
            for (int x : adj[cur]) {
                if (dist[x]==INT_MAX) {
                    dist[x] = dist[cur]+1;
                    q.push(x);
                }
            }
        }
    };
    bfs(d_007,--s); bfs(d_null,--d); bfs(d_a,--a); bfs(d_b,--b);
    int ans = -1;
    if (d_007[a]!=d_007[b]) {
        chmax(ans,min(d_null[a]-d_007[a],d_null[b]-d_007[b]));
    } else {
        if (d_null[a]!=d_null[b]) {
            chmax(ans,min(min(d_null[a],d_null[b])-d_007[a],max(d_null[a],d_null[b])-d_007[a]-1));
        } else {
            int split_null = -1, split_007 = -1;
            for (int i=0;i<n;i++) {
                if (d_a[i]==d_b[i]) {
                    if (d_a[i]+d_null[i]==d_null[a]) {
                        if (split_null==-1 || d_a[i]<d_a[split_null]) {
                            split_null = i;
                        }
                    }
                    if (d_a[i]+d_007[i]==d_007[a]) {
                        if (split_007==-1 || d_a[i]<d_a[split_007]) {
                            split_007 = i;
                        }
                    }
                }
            }
            chmax(ans,d_null[a]-d_007[a]-1);
            
            if (d_a[split_007]<=d_a[split_null]) {
                chmax(ans,d_null[a]-d_007[a]);
            }
        }
    } cout << ans << '\n';
    /*
    bfs
    if times for 007 are off by 1
    then only one route, so check for both server

    if times are the same:
    if times for null are not the same as these: take smaller time for null

    if all four times are the same:
    do the bfs from both servers to find best split points for 007 and null, and compare them
    */
}

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