Submission #82368

#	Time	Username	Problem	Language	Result	Execution time	Memory
82368		minhtung0404	007 (CEOI14_007)	C++17	0 / 100	640 ms	15916 KiB

007

#include<bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;

vector <int> adj[N];
int n, m, s, d, a, b;
int ck[N];

bool check(int num){
    for (int i = 1; i <= n; i++) ck[i] = 0;
    queue <int> mq, mq2; mq.push(d); ck[d] = 1;
    while (mq.size()){
        int u = mq.front();
        if (ck[u] == num+1) break;
        mq.pop();
        for (auto v : adj[u]){
            if (ck[v]) continue;
            ck[v] = ck[u] + 1;
            mq.push(v);
        }
    }
    if (ck[a] || ck[b]) return false;
    mq2.push(s); ck[s] = -1; int cnt = 1;
    while (mq2.size()){
        while (mq.size()){
            int u = mq.front();
            if (ck[u] == num+cnt+1) break;
            mq.pop();
            if (ck[u] < 0) continue;
            for (auto v : adj[u]){
                if (ck[v]) continue;
                ck[v] = ck[u] + 1;
                mq.push(v);
            }
        }

        while (mq2.size()){
            int u = mq2.front();
            if (-ck[u] == cnt+1) break;
            mq2.pop();
            for (auto v : adj[u]){
                if (ck[v] < 0) continue;
                ck[v] = ck[u] - 1;
                mq2.push(v);
            }
        }
        if (ck[a] > 0 || ck[b] > 0) return false;
        cnt++;
    }
    return true;
}

int main(){
//    freopen("SPY.inp", "r", stdin);
//    freopen("SPY.out", "w", stdout);
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &s, &d, &a, &b);
    for (int i = 1; i <= m; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int l = 0, r = n + 1, ans = -1;
    while (l != r){
        int mid = (l + r + 1) / 2;
        if (check(mid)){
            ans = mid;
            l = mid;
        }
        else{
            r = mid-1;
        }
    }
    if (check(l)) ans = l;
    printf("%d", ans);
}

Compilation message (stderr)

007.cpp: In function 'int main()':
007.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
007.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &s, &d, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

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