oj.uz

Submission #391854

# Submission time Handle Problem Language Result Execution time Memory
391854 2021-04-20T03:49:30 Z Kevin_Zhang_TW 007 (CEOI14_007) C++17
30 / 100
 324 ms 17524 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;
		}

		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:70:3: note: in expansion of macro 'DE'
   70 |   DE(a, b);
      |   ^~
007.cpp:80:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   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 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Partially correct 3 ms 4940 KB Partially correct
14 Correct 3 ms 4940 KB Output is correct
15 Partially correct 3 ms 4940 KB Partially correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 4 ms 4980 KB Output is correct
19 Partially correct 4 ms 5052 KB Partially correct
20 Partially correct 4 ms 5068 KB Partially correct
21 Correct 5 ms 4940 KB Output is correct
22 Partially correct 4 ms 5068 KB Partially correct
23 Partially correct 4 ms 5068 KB Partially correct
24 Correct 5 ms 5068 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 26 ms 6860 KB Partially correct
2 Correct 34 ms 7732 KB Output is correct
3 Partially correct 29 ms 7036 KB Partially correct
4 Correct 36 ms 7856 KB Output is correct
5 Correct 26 ms 6756 KB Output is correct
6 Correct 28 ms 7084 KB Output is correct
7 Partially correct 31 ms 7196 KB Partially correct
8 Partially correct 33 ms 7236 KB Partially correct
9 Correct 45 ms 7748 KB Output is correct
10 Partially correct 150 ms 12132 KB Partially correct
11 Correct 58 ms 9168 KB Output is correct
12 Partially correct 83 ms 10284 KB Partially correct
13 Correct 67 ms 9472 KB Output is correct
14 Correct 50 ms 8828 KB Output is correct
15 Partially correct 84 ms 10480 KB Partially correct
16 Correct 83 ms 10684 KB Output is correct
17 Partially correct 72 ms 10108 KB Partially correct
18 Correct 83 ms 10132 KB Output is correct
19 Partially correct 109 ms 11304 KB Partially correct
20 Correct 202 ms 14096 KB Output is correct
21 Correct 111 ms 12484 KB Output is correct
22 Partially correct 107 ms 11456 KB Partially correct
23 Correct 110 ms 12388 KB Output is correct
24 Partially correct 114 ms 12372 KB Partially correct
25 Correct 122 ms 12104 KB Output is correct
26 Correct 102 ms 11588 KB Output is correct
27 Partially correct 124 ms 12456 KB Partially correct
28 Partially correct 151 ms 12484 KB Partially correct
29 Partially correct 161 ms 12884 KB Partially correct
30 Correct 234 ms 14920 KB Output is correct
31 Correct 137 ms 13636 KB Output is correct
32 Partially correct 134 ms 12356 KB Partially correct
33 Correct 158 ms 12728 KB Output is correct
34 Correct 151 ms 12992 KB Output is correct
35 Correct 117 ms 12704 KB Output is correct
36 Correct 125 ms 13068 KB Output is correct
37 Correct 180 ms 14036 KB Output is correct
38 Partially correct 189 ms 13948 KB Partially correct
39 Partially correct 202 ms 13904 KB Partially correct
40 Correct 250 ms 15484 KB Output is correct
41 Partially correct 324 ms 17524 KB Partially correct