Submission #541827

#	Time	Username	Problem	Language	Result	Execution time	Memory
541827		Lobo	007 (CEOI14_007)	C++17	100 / 100	264 ms	34836 KiB

007

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, m, a,b,s1,s2;
int d[maxn][5];
vector<int> g[maxn];

void bfs(int beg, int id) {
    for(int i = 1; i <= n; i++) {
        d[i][id] = inf;
    }
    d[beg][id] = 0;
    queue<int> q; q.push(beg);

    while(q.size()) {
        int u = q.front();
        q.pop();

        for(auto v : g[u]) {
            if(d[v][id] == inf) {
                d[v][id] = d[u][id]+1;
                q.push(v);
            }
        }
    }
}

void solve() {
    cin >> n >> m;

    cin >> a >> b >> s1 >> s2;

    for(int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;

        g[u].pb(v);
        g[v].pb(u);
    }
    //bfs partindo de a e de b

    bfs(a,1);
    bfs(b,2);
    bfs(s1,3);
    bfs(s2,4);

    if(d[a][3] == d[a][4] && d[b][3] == d[b][4]) {
        //ve qual vai poder escolher para onde vai primeiro
        
        int mna = inf;
        int mnb = inf;
        for(int i = 1; i <= n; i++) {
            //a->i, i->b

            if(d[i][1] + d[i][3] == d[a][3] && d[i][1] + d[i][4] == d[a][4]) {
                mna = min(mna,d[i][3]);
            }

            if(d[i][2] + d[i][3] == d[b][3] && d[i][2] + d[i][4] == d[b][4]) {
                mnb = min(mnb,d[i][3]);
            }
        }

        cout << max(d[b][3]-d[a][3]-(mnb<mna),(int) -1) << endl;

    }
    else {
        //o b vai pro menor dele e o a acompanha

        cout << max(min(d[b][3]-d[a][3],d[b][4]-d[a][4]),(int) -1) << endl;
    }



}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

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