Submission #101474

#	Time	Username	Problem	Language	Result	Execution time	Memory
101474		dwsc	007 (CEOI14_007)	C++14	90 / 100	563 ms	26752 KiB

007

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int> adj[m];
    int s,d,a,b;
    cin >> s >> d >> a >> b;
    s--;
    d--;
    a--;
    b--;
    for (int i = 0; i < m; i++){
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    queue<int> q;
    int p1[n],p2[n];
    int dist1[n],dist2[n];
    memset(dist1,-1,sizeof(dist1));
    memset(dist2,-1,sizeof(dist2));
    dist1[s] = 0;
    dist2[d] = 0;
    q.push(s);
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < adj[u].size(); i++){
            int v = adj[u][i];
            if (dist1[v] == -1){
                dist1[v] = dist1[u]+1;
                q.push(v);
                p1[v] = u;
            }
        }
    }
    q.push(d);
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < adj[u].size(); i++){
            int v = adj[u][i];
            if (dist2[v] == -1){
                dist2[v] = dist2[u]+1;
                q.push(v);
                p2[v] = u;
            }
        }
    }
   // cout << dist1[a] << " " << dist1[b] << "\n";
   // cout << dist2[a] << " " << dist2[b] << "\n";
    if (dist2[a] < dist1[a] && dist2[b] < dist1[b]) cout << -1;
    else{
        if (dist1[a] > dist1[b]){
            swap(dist1[a],dist1[b]);
            swap(dist2[a],dist2[b]);
        }
        if (dist1[a] == dist1[b]){
            if (dist2[a] == dist2[b]){
                int fin1s = a,fin2s = b;
                int fin1d = a,fin2d = b;
                int num1 = 0,num2 = 0;
                while (fin1s != fin2s){
                    fin1s = p1[fin1s];
                    fin2s = p1[fin2s];
                    num1++;
                }
                while (fin1d != fin2d){
                    fin1d = p2[fin1d];
                    fin2d = p2[fin2d];
                    num2++;
                }
                cout << dist2[a]-dist1[a]-(num2<num1);
            }
            else if (dist2[a]+1 == dist2[b]) cout << dist2[a] - dist1[a];
            else cout << dist2[b] - dist1[b];
        }
        else if (dist1[a]+1 == dist1[b]){
            if (dist2[a] == dist2[b]) cout << dist2[b] - dist1[b];
            else if (dist2[a] +1 == dist2[b]) cout << dist2[a] - dist1[a];
            else cout << dist2[b] - dist1[b];
        }
    }
}/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
*/

Compilation message (stderr)

007.cpp: In function 'int main()':
007.cpp:32:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~

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