답안 #347544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #347544

Compilation message

Subtask #1 0.0 / 30.0

Subtask #2 0.0 / 70.0

Subtask #1
0.0 / 30.0

Subtask #2
0.0 / 70.0