oj.uz

Submission #391885

# Submission time Handle Problem Language Result Execution time Memory
391885 2021-04-20T04:44:44 Z Kevin_Zhang_TW 007 (CEOI14_007) C++17
30 / 100
 286 ms 17476 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 < max(da, db) && art <= min(da, db)) return true;
			//if (art < min(da, db)) return true;
			return false;
		}

		assert(abs(ga-gb)==1);

		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:71:3: note: in expansion of macro 'DE'
   71 |   DE(a, b);
      |   ^~
007.cpp:81:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   mid = l + r >> 1;
      |         ~~^~~

Subtask #1
9.0 / 30.0

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

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 31 ms 6924 KB Partially correct
2 Correct 38 ms 7692 KB Output is correct
3 Partially correct 29 ms 6976 KB Partially correct
4 Correct 38 ms 7800 KB Output is correct
5 Correct 31 ms 6872 KB Output is correct
6 Correct 31 ms 7120 KB Output is correct
7 Partially correct 31 ms 7284 KB Partially correct
8 Partially correct 32 ms 7328 KB Partially correct
9 Correct 42 ms 7712 KB Output is correct
10 Partially correct 150 ms 12216 KB Partially correct
11 Correct 59 ms 9156 KB Output is correct
12 Partially correct 88 ms 10276 KB Partially correct
13 Correct 66 ms 9540 KB Output is correct
14 Correct 50 ms 8820 KB Output is correct
15 Partially correct 78 ms 10444 KB Partially correct
16 Correct 83 ms 10652 KB Output is correct
17 Partially correct 71 ms 10132 KB Partially correct
18 Correct 87 ms 10148 KB Output is correct
19 Partially correct 109 ms 11316 KB Partially correct
20 Correct 198 ms 14288 KB Output is correct
21 Correct 111 ms 12476 KB Output is correct
22 Partially correct 110 ms 11444 KB Partially correct
23 Correct 109 ms 12444 KB Output is correct
24 Partially correct 106 ms 12380 KB Partially correct
25 Correct 119 ms 11948 KB Output is correct
26 Correct 103 ms 11552 KB Output is correct
27 Partially correct 137 ms 12548 KB Partially correct
28 Partially correct 135 ms 12484 KB Partially correct
29 Partially correct 147 ms 12956 KB Partially correct
30 Correct 211 ms 14916 KB Output is correct
31 Correct 151 ms 13764 KB Output is correct
32 Partially correct 136 ms 12420 KB Partially correct
33 Correct 122 ms 12680 KB Output is correct
34 Correct 152 ms 12996 KB Output is correct
35 Correct 125 ms 12708 KB Output is correct
36 Correct 121 ms 13040 KB Output is correct
37 Correct 156 ms 14092 KB Output is correct
38 Partially correct 167 ms 13856 KB Partially correct
39 Partially correct 190 ms 14000 KB Partially correct
40 Correct 211 ms 15372 KB Output is correct
41 Partially correct 286 ms 17476 KB Partially correct