Submission #101421

#	Time	Username	Problem	Language	Result	Execution time	Memory
101421		rocketninja7	007 (CEOI14_007)	C++14	100 / 100	499 ms	17768 KiB

007

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
    int N, M, s, d, a, b;
    scanf("%d%d%d%d%d%d", &N, &M, &s, &d, &a, &b);
    vector<int> adjList[N+1];
    for(int i=0;i<M;i++){
        int u, v;
        scanf("%d%d", &u, &v);
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    queue<int> proc;
    proc.push(s);
    int dists[N+1];
    for(int i=1;i<N+1;i++){
        dists[i]=-1;
    }
    dists[s]=0;
    while(!proc.empty()){
        int node=proc.front();
        proc.pop();
        for(int i=0;i<adjList[node].size();i++){
            if(dists[adjList[node][i]]==-1){
                dists[adjList[node][i]]=dists[node]+1;
                proc.push(adjList[node][i]);
            }
        }
    }
    proc.push(d);
    int distd[N+1];
    for(int i=1;i<N+1;i++){
        distd[i]=-1;
    }
    distd[d]=0;
    while(!proc.empty()){
        int node=proc.front();
        proc.pop();
        for(int i=0;i<adjList[node].size();i++){
            if(distd[adjList[node][i]]==-1){
                distd[adjList[node][i]]=distd[node]+1;
                proc.push(adjList[node][i]);
            }
        }
    }
    proc.push(a);
    int dista[N+1];
    for(int i=1;i<N+1;i++){
        dista[i]=-1;
    }
    dista[a]=0;
    while(!proc.empty()){
        int node=proc.front();
        proc.pop();
        for(int i=0;i<adjList[node].size();i++){
            if(dista[adjList[node][i]]==-1){
                dista[adjList[node][i]]=dista[node]+1;
                proc.push(adjList[node][i]);
            }
        }
    }
    proc.push(b);
    int distb[N+1];
    for(int i=1;i<N+1;i++){
        distb[i]=-1;
    }
    distb[b]=0;
    while(!proc.empty()){
        int node=proc.front();
        proc.pop();
        for(int i=0;i<adjList[node].size();i++){
            if(distb[adjList[node][i]]==-1){
                distb[adjList[node][i]]=distb[node]+1;
                proc.push(adjList[node][i]);
            }
        }
    }
    int temps=N, tempd=N;
    if(dists[a]==dists[b]&&distd[a]==distd[b]){
        for(int i=1;i<N+1;i++){
            if(dista[i]==distb[i]){
                if(dists[i]+dista[i]==dists[a]){
                    temps=min(temps, dista[i]);
                }
                if(distd[i]+dista[i]==distd[a]){
                    tempd=min(tempd, dista[i]);
                }
            }
        }
    }
    printf("%d", max(min(distd[a]-dists[a], distd[b]-dists[b]), -1)+(temps>tempd?-1:0));
    return 0;
}

Compilation message (stderr)

007.cpp: In function 'int main()':
007.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<adjList[node].size();i++){
                     ~^~~~~~~~~~~~~~~~~~~~~
007.cpp:42:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<adjList[node].size();i++){
                     ~^~~~~~~~~~~~~~~~~~~~~
007.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<adjList[node].size();i++){
                     ~^~~~~~~~~~~~~~~~~~~~~
007.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<adjList[node].size();i++){
                     ~^~~~~~~~~~~~~~~~~~~~~
007.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d", &N, &M, &s, &d, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~

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