Submission #1144058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144058		dpsaveslives	007 (CEOI14_007)	C++20	100 / 100	123 ms	16488 KiB

007

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
int d1[MAXN],d2[MAXN];
vector<int> adj[MAXN];
bool vis[MAXN];
int N,M,S,T,A,B;
void bfs(int u, int *dist){
    fill(dist+1,dist+N+1,-1);
    queue<int> q; q.push(u); dist[u] = 0;
    while(!q.empty()){
        int uu = q.front(); q.pop();
        for(auto v : adj[uu]){
            if(dist[v] == -1){
                dist[v] = dist[uu]+1;
                q.push(v);
            }
        }
    }
}
int bfs2(int u){
    fill(vis+1,vis+N+1,false);
    queue<int> q; q.push(u); vis[u] = true;
    int ans = 0;
    while(!q.empty()){
        int uu = q.front(); q.pop();
        ans = max(ans,d1[u]-d1[uu]);
        for(auto v : adj[uu]){
            if(!vis[v] && d1[v] == d1[uu]-1 && d2[v] == d2[uu]-1){
                q.push(v);
                vis[v] = true;
            }
        }
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M >> S >> T >> A >> B;
    for(int i = 0;i<M;++i){
        int u,v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    bfs(A,d1); bfs(B,d2);
    int ret1 = d1[T]-d1[S], ret2 = d2[T]-d2[S];
    if(ret1 != ret2){
        cout << max(min(ret1,ret2),-1) << "\n";
    }
    else{
        int ans1 = bfs2(S), ans2 = bfs2(T);
        //cout << ans1 << " " << ans2 << "\n";
        if(ans1+ret1 < ans2){
            cout << max(ret1-1,-1) << "\n";
        }
        else{
            cout << max(ret1,-1) << "\n";
        }
    }
    return 0;
}

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