oj.uz

Submission #391817

# Submission time Handle Problem Language Result Execution time Memory
391817 2021-04-20T03:18:37 Z Kevin_Zhang_TW 007 (CEOI14_007) C++17
0 / 100
 309 ms 17652 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 -1<< '\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:65:3: note: in expansion of macro 'DE'
   65 |   DE(a, b);
      |   ^~
007.cpp:75:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   mid = l + r >> 1;
      |         ~~^~~

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6880 KB Output isn't correct
2 Partially correct 38 ms 7756 KB Partially correct
3 Incorrect 29 ms 6992 KB Output isn't correct
4 Partially correct 40 ms 7792 KB Partially correct
5 Partially correct 28 ms 6804 KB Partially correct
6 Partially correct 27 ms 7112 KB Partially correct
7 Incorrect 34 ms 7264 KB Output isn't correct
8 Incorrect 34 ms 7252 KB Output isn't correct
9 Partially correct 48 ms 7716 KB Partially correct
10 Incorrect 161 ms 12060 KB Output isn't correct
11 Partially correct 91 ms 9168 KB Partially correct
12 Incorrect 85 ms 10308 KB Output isn't correct
13 Partially correct 73 ms 9596 KB Partially correct
14 Correct 54 ms 8880 KB Output is correct
15 Incorrect 94 ms 10448 KB Output isn't correct
16 Partially correct 108 ms 10628 KB Partially correct
17 Incorrect 81 ms 10124 KB Output isn't correct
18 Partially correct 94 ms 10132 KB Partially correct
19 Incorrect 136 ms 11320 KB Output isn't correct
20 Partially correct 232 ms 14188 KB Partially correct
21 Partially correct 136 ms 12460 KB Partially correct
22 Incorrect 136 ms 11460 KB Output isn't correct
23 Partially correct 125 ms 12332 KB Partially correct
24 Incorrect 119 ms 12272 KB Output isn't correct
25 Partially correct 118 ms 11992 KB Partially correct
26 Partially correct 105 ms 11588 KB Partially correct
27 Incorrect 128 ms 12468 KB Output isn't correct
28 Incorrect 139 ms 12440 KB Output isn't correct
29 Incorrect 175 ms 12984 KB Output isn't correct
30 Partially correct 230 ms 14952 KB Partially correct
31 Partially correct 174 ms 13636 KB Partially correct
32 Incorrect 138 ms 12380 KB Output isn't correct
33 Partially correct 130 ms 12728 KB Partially correct
34 Partially correct 168 ms 13052 KB Partially correct
35 Partially correct 141 ms 12784 KB Partially correct
36 Partially correct 152 ms 13000 KB Partially correct
37 Partially correct 175 ms 14032 KB Partially correct
38 Incorrect 175 ms 13840 KB Output isn't correct
39 Incorrect 211 ms 13868 KB Output isn't correct
40 Partially correct 220 ms 15556 KB Partially correct
41 Incorrect 309 ms 17652 KB Output isn't correct