oj.uz

Submission #391886

# Submission time Handle Problem Language Result Execution time Memory
391886 2021-04-20T04:59:30 Z Kevin_Zhang_TW 007 (CEOI14_007) C++17
0 / 100
 329 ms 17532 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;
			//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;

}
	
pair<int,int> get(int s, int *dis) {
	int len = dis[A], fr = len;
	for (int i = 1;i <= n;++i) 
		if (disa[i] == disb[i] && disa[i] + dis[i] == len)
			chmin(fr, disa[i]);
	return make_pair(len, fr);
}

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);

	int res = -1;

	if (disa[s] == disb[s]) {
		auto [la, fa] = get(s, diss);
		if (disa[d] == disb[d]) {
			auto [lb, fb] = get(d, disd);
			if (fa <= fb) {
				res = lb - la;
			}
			else {
				res = lb - la - 1;
			}
		}
//		else {
//
//		}
	}

	if (res < 0) res = -1;

	cout << res << '\n';

//	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:79:3: note: in expansion of macro 'DE'
   79 |   DE(a, b);
      |   ^~

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6920 KB Output is correct
2 Correct 33 ms 7756 KB Output is correct
3 Correct 27 ms 7036 KB Output is correct
4 Correct 41 ms 7796 KB Output is correct
5 Incorrect 29 ms 6812 KB Output isn't correct
6 Incorrect 32 ms 7136 KB Output isn't correct
7 Correct 39 ms 7236 KB Output is correct
8 Correct 31 ms 7296 KB Output is correct
9 Correct 53 ms 7808 KB Output is correct
10 Correct 145 ms 12060 KB Output is correct
11 Correct 58 ms 9228 KB Output is correct
12 Correct 83 ms 10340 KB Output is correct
13 Correct 76 ms 9568 KB Output is correct
14 Correct 63 ms 8804 KB Output is correct
15 Correct 76 ms 10436 KB Output is correct
16 Incorrect 80 ms 10632 KB Output isn't correct
17 Correct 79 ms 10088 KB Output is correct
18 Correct 97 ms 10052 KB Output is correct
19 Correct 109 ms 11228 KB Output is correct
20 Correct 189 ms 14096 KB Output is correct
21 Correct 147 ms 12484 KB Output is correct
22 Correct 154 ms 11548 KB Output is correct
23 Incorrect 149 ms 12444 KB Output isn't correct
24 Correct 108 ms 12356 KB Output is correct
25 Correct 134 ms 12000 KB Output is correct
26 Incorrect 124 ms 11588 KB Output isn't correct
27 Correct 130 ms 12536 KB Output is correct
28 Correct 182 ms 12504 KB Output is correct
29 Correct 182 ms 12908 KB Output is correct
30 Correct 242 ms 14936 KB Output is correct
31 Correct 181 ms 13636 KB Output is correct
32 Correct 135 ms 12548 KB Output is correct
33 Incorrect 163 ms 12624 KB Output isn't correct
34 Correct 179 ms 13104 KB Output is correct
35 Correct 128 ms 12752 KB Output is correct
36 Correct 163 ms 13148 KB Output is correct
37 Incorrect 187 ms 14088 KB Output isn't correct
38 Correct 205 ms 13892 KB Output is correct
39 Correct 178 ms 13956 KB Output is correct
40 Correct 269 ms 15404 KB Output is correct
41 Correct 329 ms 17532 KB Output is correct