Submission #391849

#	Time	Username	Problem	Language	Result	Execution time	Memory
391849		cheissmart	007 (CEOI14_007)	C++14	30 / 100	296 ms	17896 KiB

007

#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") ->" << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

int da[N], db[N], ds[N], dd[N];
vi G[N];

void BFS(int s, int* d) {
    d[s] = 0;
    queue<int> q({s});
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int v:G[u]) if(d[v] == -1) {
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);

    memset(da, -1, sizeof da);
    memset(db, -1, sizeof db);
    memset(ds, -1, sizeof ds);
    memset(dd, -1, sizeof dd);

    int n, m;
    cin >> n >> m;
    int s, d, a, b;
    cin >> s >> d >> a >> b;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].PB(v), G[v].PB(u);
    }
    BFS(a, da), BFS(b, db), BFS(s, ds), BFS(d, dd);
    if(da[s] != db[s]) {
        int can = min(da[d] - da[s], db[d] - db[s]);
        if(can < 0) can = -1;
        cout << can << '\n';
    } else {
        int need = INF;
        for(int i = 1; i <= n; i++) {
            if(da[i] < da[s] || db[i] < db[s] || (da[i] == da[s] && db[i] == db[s])) {
                need = min(need, dd[i]);
            }
        }
        cout << need - 1 << '\n';
    }

}

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