Submission #668570

#	Time	Username	Problem	Language	Result	Execution time	Memory
668570		RambaXGorilla	007 (CEOI14_007)	C++17	100 / 100	301 ms	16444 KiB

007

#include<cstdio>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
typedef pair <int,int> ii;
int N, M, S, D, A, B;
vector <int> adj[200010];
queue <ii> near;
int dists[2][200010] = {};
bool vis[200010] = {};
void bfs(int X, int n){
    near.push(ii(X, 0));
    while(!near.empty()){
        int node = near.front().first;
        int dist = near.front().second;
        near.pop();
        if(dists[n][node]) continue;
        dists[n][node] = dist;
        for(int i : adj[node]){
            near.push(ii(i, dist + 1));
        }
    }
}
int both(int X){
    int most;
    near.push(ii(X, 0));
    while(!near.empty()){
        int node = near.front().first;
        int dist = near.front().second;
        near.pop();
        if(vis[node] || dists[0][X] - dists[0][node] != dist || dists[1][X] - dists[1][node] != dist) continue;
        vis[node] = true;
        most = dist;
        for(int i : adj[node]){
            near.push(ii(i, dist + 1));
        }
    }
    fill(vis, vis + 200010, false);
    return most;
}
int main(){
    scanf("%d%d%d%d%d%d",&N,&M,&S,&D,&A,&B);
    for(int i = 0;i < M;i++){
        int a, b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    bfs(A, 0);
    bfs(B, 1);
    int diff1 = dists[0][D] - dists[0][S];
    int diff2 = dists[1][D] - dists[1][S];
    int ideal = max(min(diff1, diff2), -1);
    if(diff1 != diff2) printf("%d",ideal);
    else printf("%d",ideal - (ideal + both(S) < both(D)));
}

Compilation message (stderr)

007.cpp: In function 'int main()':
007.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d%d%d%d%d",&N,&M,&S,&D,&A,&B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
007.cpp: In function 'int both(int)':
007.cpp:41:12: warning: 'most' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |     return most;
      |            ^~~~

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