Submission #391820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
391820	2021-04-20T03:19:20 Z	Kevin_Zhang_TW	007 (CEOI14_007)	C++17	30 / 100	315 ms	17656 KB

007

#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: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

9.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4944 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	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	4 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	5068 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	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	26 ms	6888 KB	Partially correct
2	Correct	34 ms	7784 KB	Output is correct
3	Partially correct	28 ms	6984 KB	Partially correct
4	Correct	36 ms	7800 KB	Output is correct
5	Correct	30 ms	6840 KB	Output is correct
6	Correct	26 ms	7016 KB	Output is correct
7	Partially correct	33 ms	7236 KB	Partially correct
8	Partially correct	40 ms	7276 KB	Partially correct
9	Correct	44 ms	7680 KB	Output is correct
10	Partially correct	147 ms	12144 KB	Partially correct
11	Correct	61 ms	9220 KB	Output is correct
12	Partially correct	87 ms	10312 KB	Partially correct
13	Correct	76 ms	9532 KB	Output is correct
14	Correct	59 ms	8864 KB	Output is correct
15	Partially correct	77 ms	10408 KB	Partially correct
16	Correct	82 ms	10752 KB	Output is correct
17	Partially correct	74 ms	10176 KB	Partially correct
18	Correct	96 ms	10172 KB	Output is correct
19	Partially correct	115 ms	11320 KB	Partially correct
20	Correct	194 ms	14184 KB	Output is correct
21	Correct	153 ms	12508 KB	Output is correct
22	Partially correct	123 ms	11496 KB	Partially correct
23	Correct	115 ms	12448 KB	Output is correct
24	Partially correct	110 ms	12356 KB	Partially correct
25	Correct	113 ms	11976 KB	Output is correct
26	Correct	108 ms	11800 KB	Output is correct
27	Partially correct	130 ms	12484 KB	Partially correct
28	Partially correct	141 ms	12532 KB	Partially correct
29	Partially correct	148 ms	12932 KB	Partially correct
30	Correct	264 ms	15088 KB	Output is correct
31	Correct	143 ms	13640 KB	Output is correct
32	Partially correct	133 ms	12380 KB	Partially correct
33	Correct	128 ms	12684 KB	Output is correct
34	Correct	163 ms	13048 KB	Output is correct
35	Correct	127 ms	12768 KB	Output is correct
36	Correct	123 ms	13056 KB	Output is correct
37	Correct	163 ms	14128 KB	Output is correct
38	Partially correct	170 ms	13924 KB	Partially correct
39	Partially correct	190 ms	13956 KB	Partially correct
40	Correct	229 ms	15400 KB	Output is correct
41	Partially correct	315 ms	17656 KB	Partially correct