QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463483#8579. 경찰과 도둑Crysfly0 419ms45484kbC++176.4kb2024-07-04 21:40:442024-07-04 21:40:45

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 21:40:45]
  • 评测
  • 测评结果:0
  • 用时:419ms
  • 内存:45484kb
  • [2024-07-04 21:40:44]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
const int mod = 1e9 + 7;

struct frac {
	lint a, b;
	bool operator<(const frac &x) const { return a * x.b < b * x.a; }
	bool operator<=(const frac &x) const { return a * x.b <= b * x.a; }
	bool operator>(const frac &x) const { return x < *this; }
	bool operator>=(const frac &x) const { return x <= *this; }
	bool operator==(const frac &x) const { return a * x.b == b * x.a; }
	frac operator+(const frac &f) const { return {a + f.a, b + f.b}; }
	frac operator-(const frac &f) const { return {a - f.a, b - f.b}; }
};
const int MAXN = 100005;

vector<int> weights;
lint pfar[MAXN], far[MAXN];

namespace AllDirectionTreeDP {

// Need to implement four functions:
// E: identity
// take_vertex: add vertex on top of merged edges
// up_root: update child DP to consider parent edge values
// merge: merge two child edges
// it's good if merges are commutative (its not necessary but be careful of specifics)

using elem = lint;
elem E() { return 0; }
elem take_vertex(elem DP, int v) { return DP; }
elem up_root(elem DP, int e) { return DP + weights[e / 2]; }
elem merge(elem a, elem b) { return max(a, b); }

void dfs(int x, vector<vector<pi>> &gph, vector<int> &ord, vector<int> &pae) {
	ord.push_back(x);
	for (auto &[i, y] : gph[x]) {
		gph[y].erase(find(all(gph[y]), pi{i ^ 1, x}));
		pae[y] = (i ^ 1);
		dfs(y, gph, ord, pae);
	}
}

void solve(int n, vector<pi> edges) {
	vector<vector<pi>> gph(n);
	gph.resize(n);
	for (int i = 0; i < n - 1; i++) {
		gph[edges[i][0]].push_back({2 * i, edges[i][1]});
		gph[edges[i][1]].push_back({2 * i + 1, edges[i][0]});
	}
	vector<int> ord;
	vector<int> pae(n, -1);
	dfs(0, gph, ord, pae);
	vector<elem> dp(n, E());
	reverse(all(ord));
	for (auto &z : ord) {
		for (auto &[i, y] : gph[z]) {
			dp[z] = merge(dp[z], up_root(dp[y], i));
		}
		dp[z] = take_vertex(dp[z], z);
	}
	vector<elem> rev_dp(n, E());
	reverse(all(ord));
	for (auto &z : ord) {
		vector<elem> pref(sz(gph[z]) + 1, E());
		vector<elem> suff(sz(gph[z]) + 1, E());
		if (~pae[z])
			pref[0] = up_root(rev_dp[z], pae[z]);
		for (int i = 0; i < sz(gph[z]); i++) {
			pref[i + 1] = suff[i] = up_root(dp[gph[z][i][1]], gph[z][i][0]);
		}
		for (int i = 1; i <= sz(gph[z]); i++)
			pref[i] = merge(pref[i - 1], pref[i]);
		for (int i = sz(gph[z]) - 1; i >= 0; i--)
			suff[i] = merge(suff[i], suff[i + 1]);
		for (int i = 0; i < sz(gph[z]); i++) {
			rev_dp[gph[z][i][1]] = take_vertex(merge(pref[i], suff[i + 1]), z);
		}
	}
	for (int i = 0; i < n; i++)
		far[i] = dp[i];
	for (int i = 1; i < n; i++)
		pfar[i] = rev_dp[i];
}

} // namespace AllDirectionTreeDP

vector<pi> gph[MAXN];
lint dist[MAXN];
int par[17][MAXN], dep[MAXN], din[MAXN], dout[MAXN], piv;

void dfs(int x, int p) {
	din[x] = piv++;
	for (auto &[w, y] : gph[x]) {
		if (y != p) {
			dep[y] = dep[x] + 1;
			dist[y] = dist[x] + w;
			par[0][y] = x;
			dfs(y, x);
		}
	}
	dout[x] = piv;
}

int anc(int x, int d) {
	for (int i = 0; d; i++) {
		if (d & 1)
			x = par[i][x];
		d >>= 1;
	}
	return x;
}

int lca(int u, int v) {
	if (dep[u] > dep[v])
		swap(u, v);
	int dx = dep[v] - dep[u];
	for (int i = 0; dx; i++) {
		if (dx & 1) {
			v = par[i][v];
		}
		dx >>= 1;
	}
	if (u == v)
		return u;
	for (int i = 16; i >= 0; i--) {
		if (par[i][u] != par[i][v]) {
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][u];
}

lint farf(int x, int p) {
	if (par[0][x] == p)
		return far[x];
	return pfar[p];
}

lint distf(int x, int y) { return dist[x] + dist[y] - 2 * dist[lca(x, y)]; }

vector<array<long long, 2>> police_thief(vector<int> A, vector<int> B, vector<int> D, vector<int> P, vector<int> V1, vector<int> T, vector<int> V2) {
	int n = sz(A) + 1;
	vector<pi> edges;
	for (int i = 0; i < n - 1; i++) {
		gph[A[i]].push_back({D[i], B[i]});
		gph[B[i]].push_back({D[i], A[i]});
		weights.push_back(D[i]);
		edges.push_back({A[i], B[i]});
	}
	AllDirectionTreeDP::solve(n, edges);
	dfs(0, -1);
	for (int i = 1; i < 17; i++) {
		for (int j = 0; j < n; j++) {
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	int q = sz(P);
	vector<pi> ans;
	for (int i = 0; i < q; i++) {
		int p = P[i], t = T[i], v1 = V1[i], v2 = V2[i];
		int l = lca(p, t);
		lint d = (dist[p] - dist[l]) + (dist[t] - dist[l]);
		int W = -1, pW = -1;
		// in path (l..t]
		if (frac{dist[p] - dist[l], d} <= frac{v1, v1 + v2}) {
			W = t;
			for (int i = 16; i >= 0; i--) {
				if (dep[W] - dep[l] > (1 << i) && frac{dist[p] - dist[l] + dist[par[i][W]] - dist[l], d} > frac{v1, v1 + v2}) {
					W = par[i][W];
				}
			}
			pW = par[0][W];
		} else {
			W = p;
			for (int i = 16; i >= 0; i--) {
				if (dep[W] - dep[l] >= (1 << i) && frac{dist[p] - dist[par[i][W]], d} <= frac{v1, v1 + v2}) {
					W = par[i][W];
				}
			}
			pW = W;
			W = par[0][W];
		}
		if (v1 <= v2) {
			auto z = frac{distf(p, W) + farf(W, pW), v1};
			ans.push_back({z.a, z.b});
		} else {
			auto in = [&](int s, int t) { return din[s] <= din[t] && dout[t] <= dout[s]; };
			auto predicate = [&](int q) {
				int qw = -1;
				if (in(q, p))
					qw = anc(p, dep[p] - dep[q] - 1);
				else
					qw = par[0][q];
				lint dd = distf(p, q);
				frac k1 = {farf(q, qw) + dd, v1};
				frac k2 = {2 * dd - d, v1 - v2};
				if (k1 <= k2)
					return make_pair(true, k1);
				else
					return make_pair(false, k2);
			}; // false -> true
			auto p1 = predicate(t);
			if (p1.first == 0) {
				ans.push_back({p1.second.a, p1.second.b});
				continue;
			}
			auto p2 = predicate(W);
			if (p2.first == 1) {
				ans.push_back({p2.second.a, p2.second.b});
				continue;
			}
			int l = lca(W, t);
			auto pl = predicate(l);
			if (pl.first) {
				int v = W;
				for (int i = 16; i >= 0; i--) {
					if (dep[v] - dep[l] > (1 << i) && predicate(par[i][v]).first == 0) {
						v = par[i][v];
					}
				}
				auto dap = max(predicate(v).second, predicate(par[0][v]).second);
				ans.push_back({dap.a, dap.b});
			} else {
				int v = t;
				for (int i = 16; i >= 0; i--) {
					if (dep[v] - dep[l] > (1 << i) && predicate(par[i][v]).first) {
						v = par[i][v];
					}
				}
				auto dap = max(predicate(v).second, predicate(par[0][v]).second);
				ans.push_back({dap.a, dap.b});
			}
		}
	}

	return ans;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 15
Accepted
time: 2ms
memory: 14352kb

input:

2 1
0 1 1
1 1000000 0 1000000

output:

moonrabbit2
1 1000000

result:

ok 2 lines

Test #2:

score: -15
Wrong Answer
time: 7ms
memory: 13988kb

input:

5000 5000
0 1 33612
1 2 364922
2 3 690361
3 4 936229
4 5 481430
5 6 990836
6 7 530318
7 8 809490
8 9 220360
9 10 2821
10 11 245681
11 12 545618
12 13 439038
13 14 750751
14 15 712817
15 16 178970
16 17 906394
17 18 294106
18 19 413472
19 20 395779
20 21 208193
21 22 374509
22 23 467478
23 24 211975
...

output:

moonrabbit2
74345126 12231
2141302600 31817
977131971 525511
1153824435 206157
1093602993 252970
1152577327 29996
2425408314 297482
727256921 386859
1986719014 394159
838512644 275337
2405376736 566803
973664128 531078
685039389 616324
2418996397 253035
1655204376 673807
2063972802 44840
1230097402 ...

result:

wrong answer 5th lines differ - expected: '384608145 68719', found: '1153824435 206157'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #95:

score: 0
Wrong Answer
time: 135ms
memory: 45484kb

input:

100000 100000
0 1 213617
1 2 967030
2 3 775032
3 4 505755
4 5 584670
5 6 478373
6 7 934089
7 8 274771
8 9 94919
9 10 201468
10 11 555776
11 12 530533
12 13 812779
13 14 78486
14 15 35907
15 16 613290
16 17 115129
17 18 414055
18 19 290156
19 20 373454
20 21 778454
21 22 337075
22 23 555529
23 24 974...

output:

moonrabbit2
48884074951 292792
13147147341 458303
13479380354 128689
27340670843 215559
28148697691 499660
13341326497 259690
48595680094 307094
44557181788 462428
32961396067 566507
49578768583 860478
41272537702 153615
40820157590 454333
26803960218 240315
45525041839 174790
49810508741 249866
435...

result:

wrong answer 4th lines differ - expected: '1225398214 11699', found: '13479380354 128689'

Subtask #4:

score: 0
Wrong Answer

Test #100:

score: 0
Wrong Answer
time: 55ms
memory: 34064kb

input:

100000 100000
0 1 308120
0 2 334554
0 3 784231
0 4 200542
0 5 322271
0 6 145147
0 7 701703
0 8 697197
0 9 230649
0 10 66406
0 11 192060
0 12 646979
0 13 994898
0 14 790273
0 15 857997
0 16 500846
0 17 614504
0 18 116003
0 19 860435
0 20 408561
0 21 807567
0 22 865625
0 23 912380
0 24 159361
0 25 445...

output:

moonrabbit2
1881133 342039
1365560 189840
1904664 146478
1970494 11123
1619685 16108
836019 771771
1139409 399295
1098511 681253
1255719 107615
1310172 102267
1678613 187200
1568008 126217
1621523 688489
528290 228877
675740 326129
1418730 49439
1302170 122766
1576107 151377
1792279 741719
1475969 7...

result:

wrong answer 3rd lines differ - expected: '4877 678', found: '1365560 189840'

Subtask #5:

score: 0
Wrong Answer

Test #107:

score: 0
Wrong Answer
time: 110ms
memory: 36596kb

input:

100000 100000
79032 30329 248444
88464 37167 111467
39863 17716 351134
54587 41263 457638
29720 44292 788955
35224 34773 21953
35197 81607 854881
10506 53579 730874
42849 18020 284719
11562 2134 691047
9748 66972 829044
40305 74689 96507
29530 57073 963318
60683 93450 502599
31421 18784 58037
38493 ...

output:

moonrabbit2
2467705 357807
6853519 638322
404573654 473209
2928200 596526
2635493 429398
2477489 329431
858933 245050
4529473 93542
302027555 226746
362270730 88462
310246991 288097
384855003 803454
358841914 355202
292335543 361114
367627986 90537
3835425 313089
354676453 541540
451874933 381408
45...

result:

wrong answer 5th lines differ - expected: '1464100 298263', found: '2928200 596526'

Subtask #6:

score: 0
Wrong Answer

Test #150:

score: 0
Wrong Answer
time: 54ms
memory: 33332kb

input:

100000 100000
93969 0 382662
93969 1 79501
93969 2 520957
93969 3 376570
93969 4 150693
93969 5 541083
93969 6 597220
93969 7 265149
93969 8 197919
93969 9 640117
93969 10 696733
93969 11 275493
93969 12 168554
93969 13 676861
93969 14 883069
93969 15 323396
93969 16 378012
93969 17 862488
93969 18 ...

output:

moonrabbit2
1382657 544032
463806 547769
1039621 502219
1153977 956794
1382657 259660
991144 285699
1054453 867241
1382657 516889
1382657 143336
1026650 816496
351279 557336
1382657 318712
1382657 458677
1382657 282536
1271828 863911
1382657 66063
1242824 671259
1014021 275352
658992 562229
993770 1...

result:

wrong answer 5th lines differ - expected: '67881 56282', found: '1153977 956794'

Subtask #7:

score: 0
Wrong Answer

Test #156:

score: 0
Wrong Answer
time: 226ms
memory: 42484kb

input:

100000 100000
14404 85036 1
16085 23033 46643
26279 34617 1
80367 35294 1
67695 57594 1
78450 39315 1
62640 36792 1
16192 15790 1
31390 63335 1
26051 33567 1
35882 27009 1
10252 23161 43001
29996 64903 7575
1460 99182 31033
85422 67493 796
27279 68234 36580
44622 79868 5109
87113 52694 40225
49912 7...

output:

moonrabbit2
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 2...

result:

wrong answer 2nd lines differ - expected: '1 1', found: '299999 299999'

Subtask #8:

score: 0
Wrong Answer

Test #176:

score: 0
Wrong Answer
time: 419ms
memory: 43000kb

input:

100000 100000
55628 58606 40689
5784 15690 24257
72720 4206 1
69608 99473 7530
48167 78928 1
53941 38396 1
51953 39907 1
97834 17721 14667
88387 64737 1
94122 38165 1
58616 20038 1
90640 40598 31512
84598 84729 9557
39311 27869 48827
95273 81340 27050
51941 93655 1
5842 33582 44082
5873 68938 1
5918...

output:

moonrabbit2
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 299999
299999 2...

result:

wrong answer 2nd lines differ - expected: '1 1', found: '299999 299999'

Subtask #9:

score: 0
Skipped

Dependency #1:

0%