oj.uz

답안 #59188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59188 2018-07-21T01:10:03 Z Benq 007 (CEOI14_007) C++14
0 / 100
 405 ms 102200 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 200001;

int n,m,s,d,a,b;
vi adj[MX];
int dist[2][MX];

void genDist(int k) {
    queue<int> q;
    FOR(i,1,n+1) dist[k][i] = MOD;
    if (k == 0) {
        dist[k][a] = 0; q.push(a);
    } else {
        dist[k][b] = 0; q.push(b);
    }
    while (sz(q)) {
        int x = q.front(); q.pop();
        for (int i: adj[x]) if (dist[k][i] == MOD) {
            dist[k][i] = dist[k][x]+1;
            q.push(i);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    cin >> s >> d >> a >> b;
    F0R(i,m) {
        int x,y; cin >> x >> y;
        adj[x].pb(y), adj[y].pb(x);
    }
    genDist(0), genDist(1);
    cout << max(min(dist[0][d]-dist[0][s],dist[1][d]-dist[1][s]),-1);
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 6 ms 5096 KB Output is correct
3 Correct 7 ms 5336 KB Output is correct
4 Incorrect 7 ms 5336 KB Output isn't correct
5 Incorrect 7 ms 5448 KB Output isn't correct
6 Correct 6 ms 5448 KB Output is correct
7 Correct 8 ms 5448 KB Output is correct
8 Incorrect 8 ms 5448 KB Output isn't correct
9 Correct 8 ms 5448 KB Output is correct
10 Correct 8 ms 5448 KB Output is correct
11 Correct 8 ms 5484 KB Output is correct
12 Incorrect 7 ms 5496 KB Output isn't correct
13 Correct 9 ms 5500 KB Output is correct
14 Incorrect 8 ms 5500 KB Output isn't correct
15 Correct 7 ms 5500 KB Output is correct
16 Incorrect 6 ms 5520 KB Output isn't correct
17 Incorrect 8 ms 5520 KB Output isn't correct
18 Incorrect 8 ms 5520 KB Output isn't correct
19 Correct 9 ms 5588 KB Output is correct
20 Correct 8 ms 5588 KB Output is correct
21 Correct 7 ms 5604 KB Output is correct
22 Correct 8 ms 5612 KB Output is correct
23 Correct 8 ms 5620 KB Output is correct
24 Incorrect 10 ms 5620 KB Output isn't correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 7688 KB Output is correct
2 Incorrect 36 ms 9064 KB Output isn't correct
3 Correct 39 ms 9064 KB Output is correct
4 Incorrect 64 ms 10404 KB Output isn't correct
5 Correct 46 ms 10404 KB Output is correct
6 Correct 37 ms 10680 KB Output is correct
7 Correct 43 ms 11572 KB Output is correct
8 Correct 44 ms 12040 KB Output is correct
9 Incorrect 51 ms 13504 KB Output isn't correct
10 Correct 284 ms 22932 KB Output is correct
11 Incorrect 65 ms 22932 KB Output isn't correct
12 Correct 83 ms 23276 KB Output is correct
13 Incorrect 92 ms 23848 KB Output isn't correct
14 Correct 72 ms 24240 KB Output is correct
15 Correct 97 ms 26996 KB Output is correct
16 Correct 123 ms 28768 KB Output is correct
17 Correct 92 ms 29528 KB Output is correct
18 Incorrect 107 ms 30764 KB Output isn't correct
19 Correct 154 ms 34488 KB Output is correct
20 Incorrect 317 ms 42952 KB Output isn't correct
21 Incorrect 179 ms 42976 KB Output isn't correct
22 Correct 99 ms 43728 KB Output is correct
23 Correct 169 ms 46560 KB Output is correct
24 Correct 183 ms 48256 KB Output is correct
25 Incorrect 112 ms 49804 KB Output isn't correct
26 Correct 131 ms 51260 KB Output is correct
27 Correct 183 ms 54028 KB Output is correct
28 Correct 170 ms 56072 KB Output is correct
29 Correct 199 ms 60056 KB Output is correct
30 Incorrect 259 ms 67796 KB Output isn't correct
31 Incorrect 156 ms 68480 KB Output isn't correct
32 Correct 163 ms 69512 KB Output is correct
33 Correct 126 ms 71792 KB Output is correct
34 Incorrect 180 ms 74360 KB Output isn't correct
35 Incorrect 142 ms 76076 KB Output isn't correct
36 Incorrect 145 ms 78516 KB Output isn't correct
37 Correct 218 ms 81896 KB Output is correct
38 Correct 187 ms 84024 KB Output is correct
39 Correct 201 ms 86668 KB Output is correct
40 Incorrect 273 ms 92640 KB Output isn't correct
41 Correct 405 ms 102200 KB Output is correct