oj.uz

Submission #391831

# Submission time Handle Problem Language Result Execution time Memory
391831 2021-04-20T03:26:33 Z Kevin_Zhang_TW 007 (CEOI14_007) C++17
0 / 100
 293 ms 17480 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 200010, inf = 1e9;

int n, m, s, d, A, B;
vector<int> edge[MAX_N];

int diss[MAX_N], disd[MAX_N], disa[MAX_N], disb[MAX_N];

void get_dis(int s, int *dis) {
	fill(dis, dis + n + 1, inf);

	queue<int> q;
	q.emplace(s); dis[s] = 0;
	while (q.size()) {
		int x = q.front(); q.pop();
		for (int u : edge[x])
			if (chmin(dis[u], dis[x] + 1))
				q.emplace(u);
	}
}
bool valid(int rest) {
	auto test = [&](int x) {
		int art = diss[x] + rest;
		int ga = art + disa[x], gb = art + disb[x];
		if (max(disa[x], disb[x]) > 1) return false;

		int da = disd[A], db = disd[B];

		if (min(disa[x], disb[x]) == 1) {
			if (art <= min(da, db)) return true;
			return false;
		}

		if (ga < da && gb < db) return true;

		return false;
	};

	for (int i = 1;i <= n;++i)
		if (test(i)) return true;
	return false;

}
	
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> s >> d >> A >> B;
	for (int a, b, i = 0;i < m;++i) {
		cin >> a >> b;
		DE(a, b);
		edge[a].pb(b), edge[b].pb(a);
	}
	get_dis(s, diss), get_dis(d, disd);
	get_dis(A, disa), get_dis(B, disb);

	if (!valid(0)) return puts("-1"), 0;

	int l = 0, r = n, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (valid(mid+1))
			l = mid + 1;
		else
			r = mid;
	}
	cout << l << '\n';
}

Compilation message

007.cpp: In function 'int32_t main()':
007.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
007.cpp:66:3: note: in expansion of macro 'DE'
   66 |   DE(a, b);
      |   ^~
007.cpp:76:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   mid = l + r >> 1;
      |         ~~^~~

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 6876 KB Output isn't correct
2 Partially correct 35 ms 7676 KB Partially correct
3 Incorrect 29 ms 6956 KB Output isn't correct
4 Partially correct 34 ms 7900 KB Partially correct
5 Partially correct 29 ms 6852 KB Partially correct
6 Partially correct 28 ms 7040 KB Partially correct
7 Incorrect 37 ms 7236 KB Output isn't correct
8 Incorrect 31 ms 7316 KB Output isn't correct
9 Partially correct 42 ms 7688 KB Partially correct
10 Incorrect 145 ms 12120 KB Output isn't correct
11 Partially correct 58 ms 9164 KB Partially correct
12 Incorrect 93 ms 10404 KB Output isn't correct
13 Partially correct 72 ms 9548 KB Partially correct
14 Correct 51 ms 8860 KB Output is correct
15 Incorrect 77 ms 10384 KB Output isn't correct
16 Partially correct 83 ms 10744 KB Partially correct
17 Incorrect 73 ms 10108 KB Output isn't correct
18 Partially correct 80 ms 10100 KB Partially correct
19 Incorrect 121 ms 11244 KB Output isn't correct
20 Partially correct 202 ms 14160 KB Partially correct
21 Partially correct 111 ms 12488 KB Partially correct
22 Incorrect 115 ms 11664 KB Output isn't correct
23 Partially correct 113 ms 12364 KB Partially correct
24 Incorrect 107 ms 12356 KB Output isn't correct
25 Partially correct 111 ms 11900 KB Partially correct
26 Partially correct 103 ms 11592 KB Partially correct
27 Incorrect 129 ms 12484 KB Output isn't correct
28 Incorrect 135 ms 12488 KB Output isn't correct
29 Incorrect 150 ms 12912 KB Output isn't correct
30 Partially correct 228 ms 14972 KB Partially correct
31 Partially correct 139 ms 13704 KB Partially correct
32 Incorrect 130 ms 12352 KB Output isn't correct
33 Partially correct 126 ms 12616 KB Partially correct
34 Partially correct 153 ms 13128 KB Partially correct
35 Partially correct 136 ms 12900 KB Partially correct
36 Partially correct 123 ms 12976 KB Partially correct
37 Partially correct 156 ms 14068 KB Partially correct
38 Incorrect 166 ms 14024 KB Output isn't correct
39 Incorrect 175 ms 13928 KB Output isn't correct
40 Partially correct 214 ms 15388 KB Partially correct
41 Incorrect 293 ms 17480 KB Output isn't correct