oj.uz

Submission #347544

# Submission time Handle Problem Language Result Execution time Memory
347544 2021-01-13T07:55:44 Z ACmachine 007 (CEOI14_007) C++17
0 / 100
 268 ms 23020 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}

    
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
	int n, m;
    cin >> n >> m;
    int s, d, a, b;
    cin >> s >> d >> a >> b;
    s--; d--; a--; b--;
    vector<vi> adj(n);
    REP(i, m){
        int u, v;
        cin >> u >> v;
        v--; u--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    auto bfs = [&](int st){
        vector<int> dist(n, -1);
        dist[st] = 0;
        queue<int> q;
        q.push(st);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(int x : adj[v]){
                if(dist[x] == -1){
                    dist[x] = dist[v] + 1;
                    q.push(x);
                }
            }
        }
        return dist;
    };
    vi dist_a = bfs(s);
    vi dist_d = bfs(d);
    bool can = false;
    if(dist_a[a] <= dist_d[a] && dist_a[b] <= dist_d[b])
        can = true;
    if(!can){
        cout << -1 << "\n";
        return 0;
    }
    int ans = min(dist_d[a] - dist_a[a], dist_d[b] - dist_a[b]);
    cout << ans << "\n";
    return 0;
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 1 ms 364 KB Output isn't correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Incorrect 1 ms 364 KB Output isn't correct
13 Correct 1 ms 364 KB Output is correct
14 Incorrect 1 ms 364 KB Output isn't correct
15 Correct 1 ms 364 KB Output is correct
16 Incorrect 1 ms 364 KB Output isn't correct
17 Incorrect 1 ms 512 KB Output isn't correct
18 Incorrect 1 ms 364 KB Output isn't correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Incorrect 1 ms 364 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3436 KB Output is correct
2 Incorrect 31 ms 4716 KB Output isn't correct
3 Correct 22 ms 3552 KB Output is correct
4 Incorrect 29 ms 4844 KB Output isn't correct
5 Correct 20 ms 3308 KB Output is correct
6 Correct 20 ms 3692 KB Output is correct
7 Correct 23 ms 3948 KB Output is correct
8 Correct 23 ms 3948 KB Output is correct
9 Incorrect 36 ms 4844 KB Output isn't correct
10 Correct 139 ms 13804 KB Output is correct
11 Incorrect 47 ms 7148 KB Output isn't correct
12 Correct 67 ms 8940 KB Output is correct
13 Incorrect 54 ms 7660 KB Output isn't correct
14 Correct 43 ms 6508 KB Output is correct
15 Correct 70 ms 8940 KB Output is correct
16 Correct 72 ms 9452 KB Output is correct
17 Correct 61 ms 8428 KB Output is correct
18 Incorrect 67 ms 8428 KB Output isn't correct
19 Correct 98 ms 10988 KB Output is correct
20 Incorrect 176 ms 16876 KB Output isn't correct
21 Incorrect 104 ms 12524 KB Output isn't correct
22 Correct 92 ms 10732 KB Output is correct
23 Correct 98 ms 12268 KB Output is correct
24 Correct 100 ms 12140 KB Output is correct
25 Incorrect 100 ms 11500 KB Output isn't correct
26 Correct 87 ms 10860 KB Output is correct
27 Correct 110 ms 12396 KB Output is correct
28 Correct 114 ms 12396 KB Output is correct
29 Correct 144 ms 14020 KB Output is correct
30 Incorrect 199 ms 18156 KB Output isn't correct
31 Incorrect 127 ms 14188 KB Output isn't correct
32 Correct 112 ms 12268 KB Output is correct
33 Correct 108 ms 12652 KB Output is correct
34 Incorrect 129 ms 13292 KB Output isn't correct
35 Incorrect 104 ms 12780 KB Output isn't correct
36 Incorrect 111 ms 13292 KB Output isn't correct
37 Correct 122 ms 14956 KB Output is correct
38 Correct 148 ms 14700 KB Output is correct
39 Correct 146 ms 14700 KB Output is correct
40 Incorrect 189 ms 18156 KB Output isn't correct
41 Correct 268 ms 23020 KB Output is correct