oj.uz

Submission #391830

# Submission time Handle Problem Language Result Execution time Memory
391830 2021-04-20T03:25:20 Z Kevin_Zhang_TW 007 (CEOI14_007) C++17
30 / 100
 286 ms 17508 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
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 5036 KB Output is correct
3 Partially correct 3 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 4996 KB Partially correct
10 Correct 4 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 4 ms 4940 KB Partially correct
14 Correct 3 ms 4940 KB Output is correct
15 Partially correct 3 ms 4944 KB Partially correct
16 Correct 4 ms 4940 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 5 ms 5068 KB Output is correct
19 Partially correct 4 ms 4988 KB Partially correct
20 Partially correct 4 ms 5068 KB Partially correct
21 Correct 3 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 4 ms 5068 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 27 ms 6924 KB Partially correct
2 Correct 34 ms 7796 KB Output is correct
3 Partially correct 28 ms 7000 KB Partially correct
4 Correct 37 ms 7884 KB Output is correct
5 Correct 26 ms 6860 KB Output is correct
6 Correct 25 ms 7116 KB Output is correct
7 Partially correct 32 ms 7236 KB Partially correct
8 Partially correct 31 ms 7268 KB Partially correct
9 Correct 45 ms 7628 KB Output is correct
10 Partially correct 147 ms 12104 KB Partially correct
11 Correct 58 ms 9188 KB Output is correct
12 Partially correct 82 ms 10228 KB Partially correct
13 Correct 68 ms 9540 KB Output is correct
14 Correct 51 ms 8768 KB Output is correct
15 Partially correct 79 ms 10332 KB Partially correct
16 Correct 85 ms 10744 KB Output is correct
17 Partially correct 73 ms 10052 KB Partially correct
18 Correct 91 ms 10068 KB Output is correct
19 Partially correct 118 ms 11328 KB Partially correct
20 Correct 197 ms 14212 KB Output is correct
21 Correct 129 ms 12460 KB Output is correct
22 Partially correct 117 ms 11528 KB Partially correct
23 Correct 118 ms 12452 KB Output is correct
24 Partially correct 112 ms 12264 KB Partially correct
25 Correct 134 ms 11972 KB Output is correct
26 Correct 125 ms 11624 KB Output is correct
27 Partially correct 128 ms 12508 KB Partially correct
28 Partially correct 143 ms 12440 KB Partially correct
29 Partially correct 158 ms 12944 KB Partially correct
30 Correct 234 ms 14848 KB Output is correct
31 Correct 149 ms 13716 KB Output is correct
32 Partially correct 143 ms 12364 KB Partially correct
33 Correct 127 ms 12724 KB Output is correct
34 Correct 151 ms 12996 KB Output is correct
35 Correct 130 ms 12688 KB Output is correct
36 Correct 120 ms 13088 KB Output is correct
37 Correct 174 ms 14148 KB Output is correct
38 Partially correct 164 ms 13840 KB Partially correct
39 Partially correct 174 ms 13872 KB Partially correct
40 Correct 213 ms 15408 KB Output is correct
41 Partially correct 286 ms 17508 KB Partially correct