QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#431871	#5515. Cat Exercise	hansiyuan^#	54	204ms	71664kb	C++14	2.7kb	2024-06-06 11:22:14	2024-06-06 11:22:16

Judging History

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

[2024-06-06 11:22:16]
评测

测评结果：54
用时：204ms
内存：71664kb

查看

[2024-06-06 11:22:14]
提交

answer

#include <bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1
using namespace std;
typedef long long lol;
const int N=2e5+5;
int n;
int dui[N];
vector<int> g[N];
namespace solve1{
	bool vis[N];
	int dep[N];
	void dfs0(int u,int fa){
		for(int v:g[u])
			if(v!=fa && !vis[v])
				dep[v]=dep[u]+1, dfs0(v,u);
	}
	int find_mx(int u,int fa){
		int res=u;
		for(int v:g[u])
			if(v!=fa && !vis[v]) 
				res=max(find_mx(v,u),res);
		return res;
	}
	int solve(int u){
		int res=0;
		dep[u] = 0;
		dfs0(u,0);
		vis[u] = 1;
		for(int v:g[u]){
			if(vis[v]) continue;
			int x = find_mx(v,u);
			res = max(dep[x]+solve(x),res);
		}
		return res;
	}
	void main(){
		printf("%d\n",solve(n));
	}
}
namespace solve2{
	lol dep[N],fa[N][20];
	int dfl[N],dfr[N],pt[N],tim;
	int mx[N<<2],lz[N<<2];
	void dfs0(int u,int Fa){
		dfl[u]=++tim;
		pt[tim] = u;
		for(int v:g[u]){
			if(v == Fa) continue;
			dep[v] = dep[u]+1;
			fa[v][0] = u;
			for(int i=1;i<=16;i++)
				fa[v][i] = fa[fa[v][i-1]][i-1];
			dfs0(v,u);
		}
		dfr[u] = tim;
	}
	int Lca(int a,int b){
		if(dep[a] < dep[b]) swap(a,b);
		for(int i=16;i>=0;i--)
			if(dep[fa[a][i]] >= dep[b])
				a = fa[a][i];
		if(a==b) return a;
		for(int i=16;i>=0;i--)
			if(fa[a][i] != fa[b][i])
				a=fa[a][i], b=fa[b][i];
		return fa[a][0];
	}
	void build(int u,int l,int r){
		if(l==r) {mx[u] = pt[l]; return;}
		int mid = (l+r)>>1;
		build(ls,l,mid); build(rs,mid+1,r);
		mx[u] = max(mx[ls],mx[rs]);
	}
	void update(int u,int l,int r,int ql,int qr){
		if(ql<=l && r<=qr){
			mx[u]=0; lz[u]=1; return;
		}
		int mid = (l+r)>>1;
		if(ql<=mid) update(ls,l,mid,ql,qr);
		if(qr>mid) update(rs,mid+1,r,ql,qr);
		mx[u] = max(mx[ls],mx[rs]);
	}
	int query(int u,int l,int r,int ql,int qr){
		if(lz[u]) return 0;
		if(ql<=l && r<=qr) return mx[u];
		int mid = (l+r)>>1;
		int res=0;
		if(ql<=mid) res = max(query(ls,l,mid,ql,qr),res);
		if(qr>mid) res = max(query(rs,mid+1,r,ql,qr),res);
		return res;
	}
	lol solve(int u,int tp){
		//cout<<u<<' '<<tp<<endl;
		lol res = 0;
		for(int v:g[u]){
			if(v == fa[u][0]) continue;
			int x = query(1,1,n,dfl[v],dfr[v]);
			if(!x) continue;
			res = max(dep[x]-dep[u]+solve(x,v),res);
		}
		if(u != n){
			update(1,1,n,dfl[u],dfr[u]);
			int x = query(1,1,n,dfl[tp],dfr[tp]);
			if(x) res = max(dep[u]+dep[x]-2ll*dep[Lca(u,x)]+solve(x,tp),res);
		}
		return res;
	}
	void main(){
		dep[n] = 1;
		dfs0(n,0);
		build(1,1,n);
		printf("%lld\n",solve(n,n));
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&dui[i]);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u = dui[u]; v=dui[v];
		g[u].push_back(v);
		g[v].push_back(u);
	}
	solve2::main();
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7

Accepted

Test #1:

score: 7

Accepted

time: 0ms

memory: 16568kb

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:

result:

ok single line: '10'

Test #2:

score: 7

Accepted

time: 0ms

memory: 16196kb

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:

result:

ok single line: '10'

Test #3:

score: 7

Accepted

time: 0ms

memory: 14920kb

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:

result:

ok single line: '120'

Test #4:

score: 7

Accepted

time: 0ms

memory: 18232kb

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:

result:

ok single line: '58'

Test #5:

score: 7

Accepted

time: 0ms

memory: 16348kb

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:

result:

ok single line: '77'

Test #6:

score: 7

Accepted

time: 3ms

memory: 15024kb

input:

2
1 2
1 2

output:

result:

ok single line: '1'

Test #7:

score: 7

Accepted

time: 3ms

memory: 16168kb

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:

result:

ok single line: '38'

Test #8:

score: 7

Accepted

time: 3ms

memory: 14916kb

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:

result:

ok single line: '22'

Test #9:

score: 7

Accepted

time: 3ms

memory: 14700kb

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:

result:

ok single line: '17'

Subtask #2:

score: 7

Accepted

Dependency #1:

100%

Accepted

Test #10:

score: 7

Accepted

time: 0ms

memory: 16148kb

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:

result:

ok single line: '44850'

Test #11:

score: 7

Accepted

time: 0ms

memory: 14884kb

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:

result:

ok single line: '20638'

Test #12:

score: 7

Accepted

time: 3ms

memory: 15100kb

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:

result:

ok single line: '22062'

Test #13:

score: 7

Accepted

time: 0ms

memory: 18176kb

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:

result:

ok single line: '853'

Test #14:

score: 7

Accepted

time: 0ms

memory: 16184kb

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:

result:

ok single line: '613'

Test #15:

score: 7

Accepted

time: 0ms

memory: 15180kb

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:

result:

ok single line: '409'

Test #16:

score: 7

Accepted

time: 0ms

memory: 16112kb

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:

result:

ok single line: '448'

Subtask #3:

score: 7

Accepted

Dependency #2:

100%

Accepted

Test #17:

score: 7

Accepted

time: 3ms

memory: 15556kb

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

Accepted

time: 7ms

memory: 19772kb

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:

result:

ok single line: '5574749'

Test #19:

score: 7

Accepted

time: 6ms

memory: 18740kb

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:

result:

ok single line: '5641202'

Test #20:

score: 7

Accepted

time: 0ms

memory: 15400kb

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:

result:

ok single line: '6072'

Test #21:

score: 7

Accepted

time: 3ms

memory: 18564kb

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:

result:

ok single line: '9050'

Test #22:

score: 7

Accepted

time: 3ms

memory: 17452kb

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:

result:

ok single line: '6106'

Test #23:

score: 7

Accepted

time: 6ms

memory: 15184kb

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:

result:

ok single line: '4633'

Subtask #4:

score: 10

Accepted

Dependency #3:

100%

Accepted

Test #24:

score: 10

Accepted

time: 0ms

memory: 17088kb

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:

ok single line: '3141224'

Test #25:

score: 10

Accepted

time: 0ms

memory: 17072kb

input:

5000
1461 2143 636 1327 3099 1008 3862 764 861 517 97 1183 4533 2145 81 1238 3165 1768 363 1975 1346 3863 673 4028 4095 4189 1375 2741 4323 2221 2476 2587 2282 2955 2558 4046 3753 143 1471 1779 942 3180 532 3910 3987 3460 2800 3713 3937 4485 3372 4069 1643 2528 3473 444 2229 1544 832 4781 983 4866 1...

output:

result:

ok single line: '3161222'

Test #26:

score: 10

Accepted

time: 3ms

memory: 15340kb

input:

5000
877 2529 4583 977 3596 4179 718 4192 2653 4763 1045 626 4786 4569 2826 1750 943 780 980 2917 1006 1535 2032 566 2818 2300 4958 115 4523 3617 2454 1603 1243 3772 3845 1041 2735 4269 2453 2819 2943 2449 1770 3394 3503 4314 4538 440 3848 3521 2226 250 2937 136 4744 1341 296 4610 338 3273 3739 1795...

output:

result:

ok single line: '3104067'

Test #27:

score: 10

Accepted

time: 3ms

memory: 19728kb

input:

5000
284 728 3780 3349 2304 1667 481 2286 3992 3127 2267 2708 703 560 667 1959 4931 1860 3292 1539 1018 4125 561 2379 3331 2657 175 207 2846 4557 2747 2082 4883 2598 4770 3532 279 2778 3027 3577 3005 959 1259 2826 3888 4164 4402 1332 1296 335 4038 2094 1440 4456 293 2910 4529 3335 146 4012 468 213 8...

output:

result:

ok single line: '3028608'

Test #28:

score: 10

Accepted

time: 6ms

memory: 16932kb

input:

5000
1327 1167 4074 1668 2623 2814 3670 2255 2039 1079 4343 284 1448 2868 705 2103 1115 4015 130 4524 818 1399 4893 950 134 1936 456 1585 564 4187 4696 2144 4478 2314 2227 3117 4881 1400 58 4328 244 828 4461 4241 1487 427 2675 634 1263 2343 4781 658 3959 4366 4147 1996 264 3649 4839 1967 879 3981 29...

output:

result:

ok single line: '3236'

Test #29:

score: 10

Accepted

time: 0ms

memory: 16944kb

input:

5000
16 2342 1372 372 1890 3654 4812 4307 2689 4982 1881 1309 3863 2897 388 4031 2026 3256 4412 1080 4306 4483 2656 4089 933 1198 1096 1597 639 3609 4120 2611 559 1512 623 709 1724 4780 2136 689 3766 119 4423 1413 1904 3532 3503 2363 4081 1607 2329 1506 4638 3511 3903 4234 4949 251 4041 765 2921 358...

output:

result:

ok single line: '8215'

Test #30:

score: 10

Accepted

time: 0ms

memory: 16588kb

input:

5000
676 4812 4561 3717 4493 995 4212 1194 4445 3928 1473 2414 4514 4452 3456 496 3376 4930 1524 1436 386 3670 2231 846 4601 48 1827 946 4597 2473 242 4629 2912 2245 3138 1697 3884 3960 2085 2546 859 3779 969 2946 317 4495 2803 2547 2116 3379 2807 1722 1151 1612 2971 2201 2851 2753 3013 1650 2000 30...

output:

result:

ok single line: '5169'

Test #31:

score: 10

Accepted

time: 3ms

memory: 15096kb

input:

5000
1145 3129 1935 4752 4430 3169 1051 4710 3335 4755 262 4267 492 627 49 1826 2524 2375 4447 4721 2916 4300 3293 2387 2728 1774 279 4598 4534 4173 2809 3515 1949 346 166 973 3214 1166 2988 1707 1032 3229 2833 137 1839 1077 3094 2050 4265 4974 1364 4633 3379 3697 4223 862 4691 55 820 4431 2022 2051...

output:

result:

ok single line: '7500'

Subtask #5:

score: 0

Wrong Answer

Test #32:

score: 0

Wrong Answer

time: 136ms

memory: 71664kb

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:

21187770688

result:

wrong answer 1st lines differ - expected: '19999900000', found: '21187770688'

Subtask #6:

score: 23

Accepted

Test #39:

score: 23

Accepted

time: 0ms

memory: 16372kb

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:

result:

ok single line: '256'

Test #40:

score: 23

Accepted

time: 204ms

memory: 57560kb

input:

200000
47590 74846 33440 172120 93313 6143 118842 183554 57721 114949 56442 25767 28220 10101 116823 185481 76250 82471 149808 167830 176621 84906 178870 135367 94129 107804 33861 133096 39663 156399 193810 84691 45814 156960 107510 195808 47135 17660 119624 99945 87252 140615 92398 154908 120735 15...

output:

result:

ok single line: '432517'

Test #41:

score: 23

Accepted

time: 199ms

memory: 58780kb

input:

200000
54514 132138 136991 158483 149121 87580 164108 86612 22687 92566 45018 38190 71624 146051 34722 140067 56355 83040 61329 154797 35240 11212 70478 94271 46277 166489 110079 98582 165864 111293 15446 143673 99507 13750 83946 132565 13323 185680 63850 63999 67105 15785 85805 153610 42258 14357 1...

output:

result:

ok single line: '486019'

Test #42:

score: 23

Accepted

time: 191ms

memory: 58980kb

input:

200000
67281 123460 65755 103449 80776 37208 166821 2511 113868 129359 63375 172281 111678 75568 198230 134639 58140 171726 134196 45888 101272 137261 155291 97353 59848 119410 147885 64293 144417 117383 114431 127365 121467 94143 42470 68084 188544 176844 21694 59475 23226 123527 12303 48756 59959 ...

output:

result:

ok single line: '410237'

Subtask #7:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted