Submission #240208

#	Time	Username	Problem	Language	Result	Execution time	Memory
240208		karma	007 (CEOI14_007)	C++14	100 / 100	323 ms	24312 KiB

007

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = int(2e5) + 7;
const int logN = 18;
typedef pair<int, int> pii;

int n, m, s, d, a, b, diff1, diff2;
vector<int> adj[N], dis[2];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> m >> s >> d >> a >> b;
    for(int u, v, i = 1; i <= m; ++i) {
        cin >> u >> v;
        adj[u].pb(v), adj[v].pb(u);
    }
    function<void(int, vector<int>&)> bfs = [&](int s, vector<int>& d) {
        queue<int> q; d.resize(n + 1, 1e9);
        d[s] = 0;
        for(q.push(s); q.size(); q.pop()) {
            s = q.front();
            for(int v: adj[s]) {
                if(d[v] > d[s] + 1)
                    d[v] = d[s] + 1, q.push(v);
            }
        }
    };
    bfs(a, dis[0]), bfs(b, dis[1]);
    diff1 = dis[0][d] - dis[0][s];
    diff2 = dis[1][d] - dis[1][s];
    if(diff1 != diff2) cout << max(-1, min(diff1, diff2));
    else {
        function<int(int)> bfs = [&](int s) {
            vector<int> d; d.resize(n + 1, 1e9);
            queue<int> q; d[s] = 0;
            for(q.push(s); q.size(); q.pop()) {
                s = q.front();
                for(int v: adj[s]) {
                    if(dis[0][v] == dis[0][s] - 1 && dis[0][v] == dis[1][v] && d[v] == 1e9)
                        q.push(v), d[v] = d[s] + 1;
                }
            }
            return d[s];
        };
        cout << max(-1, diff1 - (diff1 + bfs(s) < bfs(d)));
    }
}

Compilation message (stderr)

007.cpp: In function 'int32_t main()':
007.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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