Submission #82433

#	Time	Username	Problem	Language	Result	Execution time	Memory
82433		atoiz	007 (CEOI14_007)	C++14	100 / 100	298 ms	18228 KiB

007

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <cassert>
    #include <climits>
    #include <fstream>
    #include <stack>
    #include <queue>
    #include <map>
     
    using namespace std;
     
    const string FILE_NAME = "spy";
    const string IN_FILE = FILE_NAME + ".inp";
    const string OUT_FILE = FILE_NAME + ".out";
     
    int readInt()
    {
        char ch = getchar(); int ans = 0, sgn = 1;
        while (ch == ' ' || ch == '\n') ch = getchar();
        if (ch == '-') sgn = -1, ch = getchar();
        while (47 < ch && ch < 58) ans = ans * 10 + ch - 48, ch = getchar();
        return ans * sgn;
    }
     
    const int INF = 1e8;
    const int MAX = 200010;
    int n, m;
    int s, d, a, b;
    vector< vector<int> > dist(3, vector<int>(MAX, INF));
    vector<int> deci(MAX, INF);
    vector<int> gr[MAX];
     
    int32_t main()
    {
    //	freopen(IN_FILE.c_str(), "r", stdin);
    //	freopen(OUT_FILE.c_str(), "w", stdout);
     
    	n = readInt(); m = readInt();
    	s = readInt(); d = readInt(); a = readInt(); b = readInt();
        for (int i = 0; i < m; ++i) {
    		int u = readInt(), v = readInt();
            gr[u].push_back(v);
            gr[v].push_back(u);
        }
     
     
    	dist[0][a] = 0;
    	queue<int> qu; qu.push(a);
        while (!qu.empty()) {
            int u = qu.front(); qu.pop();
            for (int v : gr[u]) {
                if (dist[0][v] == INF) {
                    dist[0][v] = dist[0][u] + 1;
                    qu.push(v);
                }
            }
        }
     
    	dist[1][b] = 0;
    	assert(qu.empty());
    	qu.push(b);
        while (!qu.empty()) {
            int u = qu.front(); qu.pop();
            for (int v : gr[u]) {
                if (dist[1][v] == INF) {
                    dist[1][v] = dist[1][u] + 1;
                    qu.push(v);
                }
            }
     
            deci[u] = min(dist[0][u], dist[1][u]);
            for (int v : gr[u]) {
                if (dist[0][v] + 1 == dist[0][u] && dist[1][v] + 1 == dist[1][u]) {
                    deci[u] = min(deci[u], deci[v]);
                }
            }
        }
     
    	dist[2][d] = 0;
    	assert(qu.empty());
    	qu.push(d);
        while (!qu.empty()) {
            int u = qu.front(); qu.pop();
            for (int v : gr[u]) {
                if (dist[2][v] == INF) {
                    dist[2][v] = dist[2][u] + 1;
                    qu.push(v);
                }
            }
        }
     
    	int ans = INF;
     
    	for (int u = 1; u <= n; ++u) {
            bool block;
            if (dist[0][s] > dist[0][u]) block = 0;
            else if (dist[1][s] > dist[1][u]) block = 0;
            else if (dist[0][s] < dist[0][u]) block = 1;
            else if (dist[1][s] < dist[1][u]) block = 1;
            else if (deci[s] <= deci[u]) block = 1;
            else block = 0;
     
            if (u == d && (!block)) {
                cout << -1;
                return 0;
            }
            if (!block) {
                ans = min(ans, dist[2][u] - 1);
            }
    	}
    	cout << ans;
    }

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