QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202083#5515. Cat Exercisejmyszka#21 1055ms20832kbC++175.8kb2023-10-05 19:09:162024-07-04 02:16:49

Judging History

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

  • [2024-07-04 02:16:49]
  • 评测
  • 测评结果:21
  • 用时:1055ms
  • 内存:20832kb
  • [2023-10-05 19:09:16]
  • 提交

answer

#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class A, class B>
ostream& operator<<(ostream& o, const pair<A, B>& p) {return o << '(' << p.first << ", " << p.second << ')';}
template<size_t Index = 0, typename... Types>
ostream& printTupleElements(ostream& o, const tuple<Types...>& t) {if constexpr (Index < sizeof...(Types)){if(Index > 0){o << ", ";}o << get<Index>(t);printTupleElements<Index + 1>(o, t);}return o;}
template<typename... Types>
ostream& operator<<(ostream& o, const tuple<Types...>& t){o << "(";printTupleElements(o, t);return o << ")";}
template<class T>
auto operator<<(ostream& o, const T& x) -> decltype(x.end(), o){o << '{';bool first = true;for (const auto& e : x){if (!first){o << ", ";}o << e;first = false;} return o << '}';}
//#define DEBUG
#ifdef DEBUG
#define fastio()
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#define check(x) if (!(x)) { cerr << "Check failed: " << #x << " in line " << __LINE__ << endl; exit(1); }
#else
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(...)
#define check(x) 
#endif
typedef long long ll;
#define pi pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
constexpr int LIM = 2e5;
constexpr int base = (1 << 18);
int tri[2 * base];
int lazy[2 * base];
vi g[LIM + 10];
int tab[LIM + 10];
ll dp[LIM + 10];
pi prep[LIM + 10];
int nxt[LIM + 10][19];
int dod[LIM + 10];
pi mx[LIM + 10][19];
int pre[LIM + 10];
int siz[LIM + 10];
int oj[LIM + 10];
int post[LIM + 10];
int aktpre = 1;
int aktpost = 1;
void cntsiz(int v, int o) {
	siz[v] = 1;
	for(auto x : g[v]) {
		if(x != o) {
			cntsiz(x, v);
			siz[v] += siz[x];
		}
	}
}
void makehld(int v, int o) {
	pi mx = {0, -1};
	for(int i = 0; i < sz(g[v]); i++) {
		if(g[v][i] != o) {
			mx = max(mx, make_pair(siz[g[v][i]], i));
		}
	}
	if(mx.nd >= 0) {
		swap(g[v][0], g[v][mx.nd]);
		oj[g[v][0]] = v;
		makehld(g[v][0], v);
		for(int i = 1; i < sz(g[v]); i++) {
			if(g[v][i] != o) {
				oj[g[v][i]] = g[v][i];
				makehld(g[v][i], v);
			}
		}
	}
}
void dfs(int v, int o) {
	pre[v] = aktpre++;
	nxt[v][0] = o;
	mx[v][0] = max(make_pair(tab[v], v), make_pair(tab[o], o));
	for(int i = 1; i <= 18; i++) {
		nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
		mx[v][i] = max(mx[v][i - 1], mx[nxt[v][i - 1]][i - 1]);
	}
	for(auto x : g[v]) {
		if(x != o) {
			dfs(x, v);
		}
	}
	post[v] = aktpost++;
}
bool czy(int a, int b) {
	return pre[a] <= pre[b] && post[a] >= post[b];
}
int dist(int v, int o) {
	if(v == o) {
		return 0;
	}
	if(pre[v] < pre[o]) {
		swap(v, o);
	}
	int ans = 0;
	for(int i = 18; i >= 0; i--) {
		if(!czy(nxt[v][i], o)) {
			ans += (1 << i);
			v = nxt[v][i];
		}
	}
	if(!czy(v, o)) {
		ans++;
		v = nxt[v][0];
	}
	for(int i = 18; i >= 0; i--) {
		if(!czy(nxt[o][i], v)) {
			ans += (1 << i);
			o = nxt[o][i];
		}
	}
	if(!czy(o, v)) {
		ans++;
		o = nxt[o][0];
	}
	return ans;
}
void spl(int v) {
	tri[2 * v] = max(tri[2 * v], lazy[v]);
	tri[2 * v + 1] = max(tri[2 * v + 1], lazy[v]);
	lazy[2 * v] = max(lazy[2 * v], lazy[v]);
	lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
	lazy[v] = 0;
}
void update(int v, int l, int r, int a, int b, int x)  {
	if(l > b || r < a) {
		return;
	}
	if(a <= l && r <= b) {
		tri[v] = max(tri[v], x);
		lazy[v] = max(lazy[v], x);
		return;
	}
	spl(v);
	int mid = (l + r) / 2;
	update(2 * v, l, mid, a, b, x);
	update(2 * v + 1, mid + 1, r, a, b, x);
	tri[v] = max(tri[v], max(tri[2 * v], tri[2 * v + 1]));
}
int query(int v, int l, int r, int a, int b)  {
	if(l > b || r < a) {
		return 0;
	}
	if(a <= l && r <= b) {
		return tri[v];
	}
	spl(v);
	int mid = (l + r) / 2;
	return max(query(2 * v, l, mid, a, b), query(2 * v + 1, mid + 1, r, a, b));
}
void upd(int v, int o, int x) {
	while(pre[v] >= pre[o]) {
		if(oj[v] == v) {
			dod[v] += x;
			if(v == 1) {
				break;
			}
			v = nxt[v][0];
		}
		else if(pre[oj[v]] >= pre[o]) {
			update(1, 1, base, pre[oj[v]], pre[v], x);
			if(oj[v] == 1) {
				break;
			}
			v = nxt[oj[v]][0];
		}
		else {
			update(1, 1, base, pre[o], pre[v], x);
			break;
		}
	}
}
int que(int v, int o) {
	int ans = 0;
	while(pre[v] >= pre[o]) {
		if(oj[v] == v) {
			ans += dod[v];
			if(v == 1) {
				break;
			}
			v = nxt[v][0];
		}
		if(pre[oj[v]] >= pre[o]) {
			ans = max(ans, query(1, 1, base, pre[oj[v]], pre[v]));
			if(oj[v] == 1) {
				break;
			}
			v = nxt[oj[v]][0];
		}
		else {
			ans = max(ans, query(1, 1, base, pre[o], pre[v]));
			break;
		}
	}
	return ans;
}
void solve() {
	//ifstream cin("nazwa.in");
	//ofstream cout("nazwa.out");
	int n;
	cin >> n;
	vector<pi>vs;
	vi pos(n + 1, 0);
	for(int i = 1; i <= n; i++) {
		cin >> tab[i];
		vs.eb(tab[i], i);
		pos[tab[i]] = i;
	}
	sort(all(vs));
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].eb(b);
		g[b].eb(a);
	}
	cntsiz(1, 1);
	makehld(1, 1);
	dfs(1, 1);
	for(auto [val, v] : vs) {
		int a = nxt[v][0];
		pi mx2 = {tab[a], a};
		for(int i = 18; i >= 0; i--) {
			if(mx[a][i].st < val) {
				mx2 = max(mx2, mx[a][i]);
				a = nxt[a][i];
			}
		}
		//debug(v, a, que(v, a));
		if(tab[a] < val) {
			int kt = pos[que(v, a)];
			dp[v] = max(dp[v], dp[kt] + dist(v, kt));
			upd(v, a, tab[v]);
			a = nxt[a][0];
		}
		else {
			upd(v, v, tab[v]);
		}
		dp[a] = max(dp[a], dp[v] + dist(v, a));
		//debug(v, dp[v]);
		if(val == n) {
			cout << dp[v] << '\n';
			return;
		}
	}
}
int main() {
	fastio();
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
}

详细

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 3ms
memory: 15932kb

input:

10
9 4 3 2 1 10 7 5 6 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

output:

10

result:

ok single line: '10'

Test #2:

score: 0
Accepted
time: 0ms
memory: 15936kb

input:

10
8 6 5 7 10 1 2 3 4 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

output:

10

result:

ok single line: '10'

Test #3:

score: 0
Accepted
time: 2ms
memory: 15920kb

input:

16
16 14 12 10 8 6 4 2 1 3 5 7 9 11 13 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

output:

120

result:

ok single line: '120'

Test #4:

score: 0
Accepted
time: 0ms
memory: 13920kb

input:

16
15 14 13 12 10 9 8 5 4 3 2 1 6 7 11 16
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

output:

58

result:

ok single line: '58'

Test #5:

score: 0
Accepted
time: 2ms
memory: 17904kb

input:

16
16 14 13 12 2 10 7 4 3 1 5 6 8 9 11 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

output:

77

result:

ok single line: '77'

Test #6:

score: 0
Accepted
time: 2ms
memory: 13912kb

input:

2
1 2
1 2

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 17988kb

input:

16
12 15 5 2 13 4 7 6 1 11 14 10 3 9 16 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

output:

38

result:

ok single line: '38'

Test #8:

score: 0
Accepted
time: 0ms
memory: 16148kb

input:

16
16 8 7 9 1 5 3 13 11 15 12 10 2 4 14 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

output:

22

result:

ok single line: '22'

Test #9:

score: 0
Accepted
time: 1ms
memory: 13836kb

input:

16
2 14 8 11 16 1 3 7 12 6 13 5 9 15 10 4
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

output:

17

result:

ok single line: '17'

Subtask #2:

score: 7
Accepted

Dependency #1:

100%
Accepted

Test #10:

score: 7
Accepted
time: 5ms
memory: 15900kb

input:

300
300 298 296 294 292 290 288 286 284 282 280 278 276 274 272 270 268 266 264 262 260 258 256 254 252 250 248 246 244 242 240 238 236 234 232 230 228 226 224 222 220 218 216 214 212 210 208 206 204 202 200 198 196 194 192 190 188 186 184 182 180 178 176 174 172 170 168 166 164 162 160 158 156 154 ...

output:

44850

result:

ok single line: '44850'

Test #11:

score: 0
Accepted
time: 5ms
memory: 13956kb

input:

300
298 30 295 294 291 289 283 280 277 275 273 271 270 268 267 29 263 262 261 28 257 256 255 27 254 253 252 249 246 245 242 241 240 238 236 230 227 226 223 221 26 217 216 214 213 210 209 204 200 197 25 196 194 193 191 185 178 24 177 176 175 173 171 23 170 169 168 164 163 160 158 157 156 153 152 151 ...

output:

20638

result:

ok single line: '20638'

Test #12:

score: 0
Accepted
time: 0ms
memory: 15920kb

input:

300
299 297 296 294 290 289 288 286 285 284 283 281 280 279 278 277 276 22 274 273 271 269 268 267 266 264 259 255 250 247 21 246 244 242 241 240 239 237 234 233 232 230 228 226 225 224 223 221 219 214 213 211 209 207 206 203 202 201 200 199 195 194 189 187 186 185 182 181 20 176 174 172 171 170 19 ...

output:

22062

result:

ok single line: '22062'

Test #13:

score: 0
Accepted
time: 0ms
memory: 16200kb

input:

300
158 241 135 137 113 59 275 127 261 65 28 112 20 101 299 263 295 209 92 129 54 86 109 105 44 102 280 220 221 196 73 74 214 224 228 91 57 38 146 274 47 56 175 232 188 173 182 143 210 130 284 257 122 141 165 237 3 167 187 278 208 85 200 155 140 283 223 273 150 191 32 216 151 204 18 63 156 258 71 31...

output:

853

result:

ok single line: '853'

Test #14:

score: 0
Accepted
time: 2ms
memory: 13960kb

input:

300
106 208 19 26 155 205 219 25 57 115 210 68 231 175 140 139 81 248 199 172 261 192 200 50 239 291 133 36 191 204 216 122 95 35 126 275 151 73 146 188 241 144 79 42 66 189 121 270 297 53 15 117 282 8 193 46 246 264 252 78 135 157 247 169 28 167 160 130 224 64 31 29 105 56 102 237 14 226 104 174 11...

output:

613

result:

ok single line: '613'

Test #15:

score: 0
Accepted
time: 3ms
memory: 18200kb

input:

300
51 181 14 64 161 90 27 26 5 67 103 156 209 36 272 229 120 33 237 71 298 32 22 260 96 182 243 300 207 72 94 221 113 124 52 167 210 282 244 173 16 184 60 228 273 152 100 172 245 131 17 191 258 21 189 192 44 25 217 112 75 121 55 57 223 137 231 145 215 270 240 54 130 285 56 139 238 115 277 4 205 129...

output:

409

result:

ok single line: '409'

Test #16:

score: 0
Accepted
time: 2ms
memory: 13956kb

input:

300
81 20 270 26 143 217 119 135 46 292 108 246 106 11 95 69 121 100 226 7 234 249 181 104 90 83 5 51 272 174 190 35 224 216 179 9 1 61 297 299 92 49 263 218 88 300 164 32 146 207 203 155 245 125 42 291 148 153 288 191 259 240 220 111 84 298 126 172 107 149 96 123 29 99 128 169 248 275 31 57 170 78 ...

output:

448

result:

ok single line: '448'

Subtask #3:

score: 7
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 7
Accepted
time: 1055ms
memory: 20832kb

input:

5000
5000 4998 4996 4994 4992 4990 4988 4986 4984 4982 4980 4978 4976 4974 4972 4970 4968 4966 4964 4962 4960 4958 4956 4954 4952 4950 4948 4946 4944 4942 4940 4938 4936 4934 4932 4930 4928 4926 4924 4922 4920 4918 4916 4914 4912 4910 4908 4906 4904 4902 4900 4898 4896 4894 4892 4890 4888 4886 4884 ...

output:

12497500

result:

ok single line: '12497500'

Test #18:

score: 0
Accepted
time: 944ms
memory: 20584kb

input:

5000
4998 4997 4995 4993 4990 457 4989 4987 4986 4984 4983 4982 4979 4977 4976 4975 4974 4970 4969 456 4968 4966 4962 455 4960 4959 4957 454 4954 4949 4948 4947 4942 4941 4937 4935 4933 4932 4931 4928 4927 4926 4925 4920 4919 453 4918 4914 4912 4911 4910 452 4906 4905 4904 4903 4902 4901 4898 451 48...

output:

5574749

result:

ok single line: '5574749'

Test #19:

score: 0
Accepted
time: 967ms
memory: 18528kb

input:

5000
4998 4997 4996 4994 4993 469 4991 4987 4986 4983 4982 4981 4978 4975 4972 4969 4968 4965 4963 4962 4958 4954 4950 468 4947 4941 4937 4934 4933 4930 4929 4927 4926 4925 467 4923 4920 4919 466 4914 4913 4912 4911 4909 4908 4907 4906 4905 4904 4903 4900 4898 4895 465 4891 4889 4886 4883 4878 464 4...

output:

5641202

result:

ok single line: '5641202'

Test #20:

score: 0
Accepted
time: 13ms
memory: 16620kb

input:

5000
1173 1790 485 3355 881 383 955 3750 3520 3284 1637 1197 4388 1451 1390 1448 3007 3857 693 3139 4082 685 3022 2716 3047 4938 4228 2858 4633 664 4848 2245 2881 3257 4962 3583 3312 3535 4835 582 3925 2799 213 3329 1865 4787 1794 3074 568 473 3812 4692 3191 4084 4609 2618 2082 3199 815 105 2448 246...

output:

6072

result:

ok single line: '6072'

Test #21:

score: 0
Accepted
time: 13ms
memory: 20612kb

input:

5000
4372 716 1450 4881 3404 3964 4918 2154 3897 4195 3426 1964 412 2905 3731 572 3641 1169 4191 1480 384 2241 4781 2952 947 677 462 1982 228 3644 3470 2911 4000 3906 4314 1127 3807 548 2578 3995 277 2498 702 789 703 2912 2846 4747 3898 1553 4495 996 782 496 1276 914 1384 3436 3626 1332 4739 3324 40...

output:

9050

result:

ok single line: '9050'

Test #22:

score: 0
Accepted
time: 8ms
memory: 18820kb

input:

5000
2717 539 4388 4260 3811 4870 921 987 2100 2686 4296 2588 4683 1893 2807 4244 4777 2293 1563 3510 3608 4656 2284 1041 4750 794 1850 3062 2743 1859 1921 856 4953 2327 460 2709 3416 491 543 4964 1272 4230 58 533 3554 2661 544 106 1849 2172 975 214 1540 3537 3105 3367 4686 2737 3206 2781 888 2844 1...

output:

6106

result:

ok single line: '6106'

Test #23:

score: 0
Accepted
time: 12ms
memory: 16528kb

input:

5000
2530 1608 3085 3987 3449 1301 346 2839 3532 1308 3663 3716 2871 2154 4443 1378 592 2688 401 2574 4723 4948 1056 1588 1681 1447 4696 260 2814 1825 2510 4393 2037 315 3804 2468 3905 2639 742 1593 4435 3769 2892 4371 3039 4763 1190 1047 1706 3216 854 2604 3047 3476 1444 283 2249 3512 3319 210 3780...

output:

4633

result:

ok single line: '4633'

Subtask #4:

score: 0
Runtime Error

Dependency #3:

100%
Accepted

Test #24:

score: 0
Runtime Error

input:

5000
2443 4316 4835 3133 2064 1132 2595 1618 709 2401 4411 1332 3143 4533 1645 1069 1141 2036 571 3166 1862 2973 2701 1056 2286 777 343 1341 891 3956 682 1789 1101 2124 642 2399 1175 430 2100 3616 916 1239 4343 4322 4012 1632 1846 4720 1484 3473 3953 690 186 1607 2095 3482 2651 4974 3954 2239 4775 3...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #32:

score: 0
Time Limit Exceeded

input:

200000
200000 199998 199996 199994 199992 199990 199988 199986 199984 199982 199980 199978 199976 199974 199972 199970 199968 199966 199964 199962 199960 199958 199956 199954 199952 199950 199948 199946 199944 199942 199940 199938 199936 199934 199932 199930 199928 199926 199924 199922 199920 199918...

output:


result:


Subtask #6:

score: 0
Wrong Answer

Test #39:

score: 0
Wrong Answer
time: 0ms
memory: 17988kb

input:

200
49 181 133 160 142 76 134 189 25 167 10 54 59 158 186 53 58 145 95 9 27 30 116 77 140 173 131 21 151 128 190 51 19 112 40 161 136 93 46 52 45 84 18 42 63 43 73 188 147 153 124 127 177 32 75 150 96 175 34 183 106 13 80 196 141 198 67 26 92 192 191 172 90 83 164 180 107 143 121 146 125 174 139 104...

output:

1048576

result:

wrong answer 1st lines differ - expected: '256', found: '1048576'

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%