oj.uz

Submission #391888

# Submission time Handle Problem Language Result Execution time Memory
391888 2021-04-20T05:02:21 Z Kevin_Zhang_TW 007 (CEOI14_007) C++17
0 / 100
 288 ms 17672 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 = -inf;

	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 {
			int ga = disa[s], gb = disb[s];
			int da = disa[d], db = disb[d];
			res = min(da, db) - ga;
		}
	}

	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);
      |   ^~
007.cpp:99:22: warning: unused variable 'gb' [-Wunused-variable]
   99 |    int ga = disa[s], gb = disb[s];
      |                      ^~

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 3 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 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 3 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 4 ms 5068 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 4996 KB Output is correct
21 Incorrect 5 ms 4940 KB Output isn't correct
22 Correct 5 ms 5068 KB Output is correct
23 Correct 4 ms 5068 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 26 ms 6876 KB Output is correct
2 Correct 33 ms 7792 KB Output is correct
3 Correct 28 ms 6984 KB Output is correct
4 Correct 34 ms 7928 KB Output is correct
5 Incorrect 25 ms 6732 KB Output isn't correct
6 Incorrect 25 ms 7116 KB Output isn't correct
7 Correct 30 ms 7260 KB Output is correct
8 Correct 31 ms 7268 KB Output is correct
9 Correct 42 ms 7664 KB Output is correct
10 Correct 148 ms 12060 KB Output is correct
11 Correct 58 ms 9180 KB Output is correct
12 Correct 81 ms 10336 KB Output is correct
13 Correct 68 ms 9596 KB Output is correct
14 Correct 52 ms 8848 KB Output is correct
15 Correct 85 ms 10356 KB Output is correct
16 Incorrect 80 ms 10740 KB Output isn't correct
17 Correct 75 ms 10108 KB Output is correct
18 Correct 78 ms 10052 KB Output is correct
19 Correct 110 ms 11252 KB Output is correct
20 Correct 190 ms 14148 KB Output is correct
21 Correct 112 ms 12560 KB Output is correct
22 Correct 108 ms 11412 KB Output is correct
23 Incorrect 112 ms 12448 KB Output isn't correct
24 Correct 110 ms 12356 KB Output is correct
25 Correct 114 ms 11976 KB Output is correct
26 Incorrect 96 ms 11540 KB Output isn't correct
27 Correct 131 ms 12496 KB Output is correct
28 Correct 149 ms 12656 KB Output is correct
29 Correct 148 ms 13068 KB Output is correct
30 Correct 211 ms 15056 KB Output is correct
31 Correct 151 ms 13764 KB Output is correct
32 Correct 167 ms 12372 KB Output is correct
33 Incorrect 123 ms 12728 KB Output isn't correct
34 Correct 149 ms 13056 KB Output is correct
35 Correct 156 ms 12716 KB Output is correct
36 Correct 154 ms 13088 KB Output is correct
37 Incorrect 155 ms 14032 KB Output isn't correct
38 Correct 160 ms 13948 KB Output is correct
39 Correct 185 ms 13960 KB Output is correct
40 Correct 221 ms 15480 KB Output is correct
41 Correct 288 ms 17672 KB Output is correct