oj.uz

Submission #391846

# Submission time Handle Problem Language Result Execution time Memory
391846 2021-04-20T03:38:35 Z Kevin_Zhang_TW 007 (CEOI14_007) C++17
30 / 100
 280 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 < 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:68:3: note: in expansion of macro 'DE'
   68 |   DE(a, b);
      |   ^~
007.cpp:78:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |   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 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 4976 KB Output is correct
9 Partially correct 3 ms 5028 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 4 ms 4984 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 4 ms 5064 KB Output is correct
19 Partially correct 4 ms 5068 KB Partially correct
20 Partially correct 4 ms 5068 KB Partially correct
21 Correct 4 ms 5028 KB Output is correct
22 Partially correct 4 ms 5068 KB Partially correct
23 Partially correct 4 ms 5072 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 25 ms 6880 KB Partially correct
2 Correct 33 ms 7756 KB Output is correct
3 Partially correct 27 ms 7016 KB Partially correct
4 Correct 35 ms 7892 KB Output is correct
5 Correct 26 ms 6812 KB Output is correct
6 Correct 26 ms 7108 KB Output is correct
7 Partially correct 30 ms 7340 KB Partially correct
8 Partially correct 31 ms 7268 KB Partially correct
9 Correct 44 ms 7748 KB Output is correct
10 Partially correct 148 ms 12088 KB Partially correct
11 Correct 57 ms 9252 KB Output is correct
12 Partially correct 83 ms 10280 KB Partially correct
13 Correct 65 ms 9536 KB Output is correct
14 Correct 50 ms 8772 KB Output is correct
15 Partially correct 81 ms 10404 KB Partially correct
16 Correct 82 ms 10720 KB Output is correct
17 Partially correct 73 ms 10076 KB Partially correct
18 Correct 79 ms 10132 KB Output is correct
19 Partially correct 107 ms 11332 KB Partially correct
20 Correct 196 ms 14176 KB Output is correct
21 Correct 109 ms 12484 KB Output is correct
22 Partially correct 105 ms 11404 KB Partially correct
23 Correct 110 ms 12404 KB Output is correct
24 Partially correct 118 ms 12356 KB Partially correct
25 Correct 110 ms 11916 KB Output is correct
26 Correct 96 ms 11532 KB Output is correct
27 Partially correct 123 ms 12432 KB Partially correct
28 Partially correct 134 ms 12444 KB Partially correct
29 Partially correct 148 ms 12968 KB Partially correct
30 Correct 205 ms 14924 KB Output is correct
31 Correct 132 ms 13568 KB Output is correct
32 Partially correct 137 ms 12368 KB Partially correct
33 Correct 126 ms 12728 KB Output is correct
34 Correct 148 ms 12976 KB Output is correct
35 Correct 115 ms 12760 KB Output is correct
36 Correct 119 ms 12988 KB Output is correct
37 Correct 165 ms 14264 KB Output is correct
38 Partially correct 158 ms 13892 KB Partially correct
39 Partially correct 172 ms 13928 KB Partially correct
40 Correct 207 ms 15392 KB Output is correct
41 Partially correct 280 ms 17476 KB Partially correct