QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69960#2545. Game with Balls and BoxesCSU2023AC ✓23ms8200kbC++142.6kb2023-01-03 16:59:062023-01-03 16:59:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-03 16:59:09]
  • 评测
  • 测评结果:AC
  • 用时:23ms
  • 内存:8200kb
  • [2023-01-03 16:59:06]
  • 提交

answer

#include <bits/stdc++.h>

template <class T>
inline void read(T &res)
{
	char ch; bool flag = false; res = 0;
	while (ch = getchar(), !isdigit(ch) && ch != '-');
	ch == '-' ? flag = true : res = ch ^ 48;
	while (ch = getchar(), isdigit(ch))
		res = res * 10 + ch - 48;
	flag ? res = -res : 0;
}

template <class T>
inline void put(T x)
{
	if (x > 9)
		put(x / 10);
	putchar(x % 10 + 48);
}

template <class T>
inline void _put(T x)
{
	if (x < 0)
		x = -x, putchar('-');
	put(x);
}

template <class T>
inline void CkMin(T &x, T y) {x > y ? x = y : 0;}
template <class T>
inline void CkMax(T &x, T y) {x < y ? x = y : 0;}
template <class T>
inline T Min(T x, T y) {return x < y ? x : y;}
template <class T>
inline T Max(T x, T y) {return x > y ? x : y;}
template <class T>
inline T Abs(T x) {return x < 0 ? -x : x;}
template <class T>
inline T Sqr(T x) {return x * x;}
// 若传入 int x 同时结果可能爆 int 应这样写 Sqr((ll)x)

using std::map;
using std::set;
using std::pair;
using std::bitset;
using std::string;
using std::vector;
using std::complex;
using std::multiset;
using std::priority_queue;

typedef long long ll;
typedef long double ld;
typedef complex<ld> com;
typedef pair<int, int> pir;
const ld pi = acos(-1.0);
const ld eps = 1e-8;
const int N = 1e5 + 5;
const ll Maxn = 1e18;
const int Minn = -1e9;
const int mod = 998244353;
int T_data, n, cm;
int p[N], cur[N], a[N], b[N];
bool vis[N];
ll ans, f[N][2][2];

inline void dfs(int x)
{
	vis[x] = true;
	cur[cm = 1] = x;
	if (x == p[x])
		return ;
	while (!vis[p[x]])
	{
		vis[cur[++cm] = p[x]] = true;
		x = p[x];
	}
	for (int i = 1; i <= cm; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				f[i][j][k] = Maxn;
	std::reverse(cur + 1, cur + cm + 1);
	f[1][0][0] = a[cur[1]];
	f[1][0][1] = a[cur[1]] + b[cur[1]];
	f[1][1][1] = b[cur[1]];
	for (int i = 1; i < cm; ++i)
		for (int j = 0; j < 2; ++j)
		{
			if (f[i][j][0] != Maxn)
			{
				CkMin(f[i + 1][j][0], f[i][j][0] + a[cur[i + 1]]);
				CkMin(f[i + 1][j][1], f[i][j][0] + a[cur[i + 1]] + b[cur[i + 1]]);
			}
			if (f[i][j][1] != Maxn)
			{
				CkMin(f[i + 1][j][1], f[i][j][1] + b[cur[i + 1]]);
				CkMin(f[i + 1][j][0], f[i][j][1] + a[cur[i + 1]]);
			}
		}
	ans += Min(Min(f[cm][0][1], f[cm][1][1]), f[cm][0][0]); 
}

int main()
{
	read(n);
	for (int i = 1; i <= n; ++i)
		read(p[i]);
	for (int i = 1; i <= n; ++i)
		read(a[i]);
	for (int i = 1; i <= n; ++i)
		read(b[i]);
	for (int i = 1; i <= n; ++i)
		if (!vis[i])
			dfs(i);
	std::cout << ans << std::endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5356kb

input:

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

output:

28

result:

ok answer is '28'

Test #2:

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

input:

1
1
1000000000
1000000000

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 11ms
memory: 8016kb

input:

100000
87816 75278 88523 80175 33693 941 20537 76213 32572 25112 82729 62404 80811 23912 36090 54871 81313 17818 99393 84407 55433 96687 31859 6172 36434 63823 78492 60489 9793 89032 65845 46121 83885 68923 19894 25769 96670 19556 22482 39806 48565 27460 93283 58127 97718 22473 88492 30322 37994 451...

output:

41405515951623

result:

ok answer is '41405515951623'

Test #4:

score: 0
Accepted
time: 16ms
memory: 7964kb

input:

99999
55223 89455 49751 23480 46437 20321 96392 20962 85747 38537 36943 52102 84354 47883 197 62426 17853 24352 51894 60538 82976 56344 34990 19700 94035 90588 83678 75745 4732 34436 61922 85469 65073 10291 79663 66957 55750 6595 83516 57744 66907 54209 42592 65664 74946 18242 77824 95633 174 61614 ...

output:

41319206163881

result:

ok answer is '41319206163881'

Test #5:

score: 0
Accepted
time: 23ms
memory: 8000kb

input:

99998
80293 8215 73061 1689 73374 75067 32887 30882 17316 71600 65476 7324 28237 55874 14932 35037 17651 78389 94030 28605 87378 72328 68958 40476 78453 29647 79855 64818 78703 69571 39319 31227 11679 57764 67215 14902 18814 73535 17174 71052 97440 38135 13296 70173 76872 56935 98281 95079 90399 783...

output:

41150520813628

result:

ok answer is '41150520813628'

Test #6:

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

input:

99997
19626 46152 98082 65755 88918 73756 85021 85411 75878 92159 33049 28904 95651 86101 30746 3373 17018 86164 777 41660 55493 71992 77912 14708 10574 63929 96504 34514 25515 19956 42291 84478 63033 79833 5263 93323 99297 29473 76198 91970 86659 93241 92533 68738 57637 49506 47293 77533 39479 4321...

output:

41321969206001

result:

ok answer is '41321969206001'

Test #7:

score: 0
Accepted
time: 9ms
memory: 6036kb

input:

99996
17209 35412 5968 1637 75788 97324 2447 55607 84373 72968 93693 47574 12259 10265 28005 29187 85944 23738 10142 98720 20011 93910 62209 63963 51132 58043 6545 40372 15482 691 47116 93263 27696 19087 34617 13969 22504 1007 73979 21388 33228 63309 99497 35711 4223 57333 85579 9334 59351 4667 1656...

output:

41430443324935

result:

ok answer is '41430443324935'

Test #8:

score: 0
Accepted
time: 18ms
memory: 8168kb

input:

100000
56331 68796 98200 79162 72121 7891 58744 9763 12380 30869 75966 26523 69524 97455 39780 56596 94721 90155 17783 6198 45206 60464 25444 94247 48066 37250 48049 9062 75441 95695 114 49458 12387 56444 40227 12083 52550 46046 99698 80736 10986 91203 55508 79953 66805 69033 67300 85729 89065 16124...

output:

41462011168854

result:

ok answer is '41462011168854'

Test #9:

score: 0
Accepted
time: 14ms
memory: 8056kb

input:

100000
48259 60866 82755 14055 66984 84105 56529 91475 64063 40786 85671 74959 78284 63630 20918 70440 91852 69772 82407 94414 59016 4500 99996 91487 15644 28952 24180 55097 23342 35475 44144 73047 88898 6009 62991 5749 93354 73501 89 82568 58212 21335 23511 28278 84378 83936 75654 77829 61782 17426...

output:

99998998014723

result:

ok answer is '99998998014723'

Test #10:

score: 0
Accepted
time: 7ms
memory: 8048kb

input:

100000
79236 98345 32080 82188 85502 43023 72153 93503 3670 88519 54276 59872 82771 10509 57118 1736 2999 73309 2454 17697 83962 65002 47311 60536 58414 11225 59949 42609 70873 14096 86245 91921 39682 98463 14768 3658 98046 12536 50084 65995 51036 13082 96129 35306 58204 46785 58167 17063 46181 9518...

output:

23849255855584

result:

ok answer is '23849255855584'

Test #11:

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

input:

100000
77358 76186 14921 95161 71694 29463 98341 41827 99358 37779 37816 29124 87667 46951 21245 97824 28911 87035 89703 90475 13853 37610 5567 44664 85210 47632 98949 60656 88344 1839 41930 32745 40161 1623 31000 97397 68919 38788 77673 76093 10253 68553 19544 23038 39726 16459 47920 77645 19198 95...

output:

23785019497067

result:

ok answer is '23785019497067'

Test #12:

score: 0
Accepted
time: 20ms
memory: 5688kb

input:

100000
71300 56748 4701 29709 55097 49325 88776 34500 22770 70158 82993 51727 49395 32990 34804 26430 71784 59042 23739 11887 74888 53807 27697 89969 77496 49687 20094 1874 56450 92682 91383 94309 2074 66528 61486 90528 1999 72111 89344 778 53707 46919 86441 53908 95237 7343 56805 35535 9417 35799 8...

output:

41215694816736

result:

ok answer is '41215694816736'

Test #13:

score: 0
Accepted
time: 18ms
memory: 4664kb

input:

100000
13493 80839 48201 84547 2489 47037 90105 68363 72 29164 8111 54616 22427 17439 17035 89163 66442 92121 62274 5549 73036 69352 57094 47064 36502 92081 70922 42900 71793 13202 28384 13070 6521 66966 47312 26096 62743 71781 68223 67098 24490 30879 91157 85618 69255 68891 45218 72322 9057 43627 6...

output:

90454486681283

result:

ok answer is '90454486681283'

Test #14:

score: 0
Accepted
time: 16ms
memory: 5768kb

input:

100000
79167 90407 43476 9127 3140 74667 77112 74177 73512 84041 64954 4500 15338 20140 55038 63709 74290 39648 90881 71234 58474 44401 34294 19390 14188 5044 91940 45552 10952 53738 75401 12746 49832 28794 18604 12262 46057 40244 37651 37479 63773 76531 83513 10325 82698 125 82096 37058 24905 46770...

output:

22300670646404

result:

ok answer is '22300670646404'

Test #15:

score: 0
Accepted
time: 11ms
memory: 5988kb

input:

100000
60279 79095 65370 17577 88816 12114 19564 32259 35910 49059 31399 67832 76258 37437 36508 34616 54505 40363 26965 54237 57419 83723 33666 93573 95957 89489 9046 96774 2314 60138 24794 91341 63367 61777 67487 23589 13404 84603 66921 61696 14919 34326 65781 48502 16133 5811 33692 36031 66510 38...

output:

51357673480090

result:

ok answer is '51357673480090'

Test #16:

score: 0
Accepted
time: 18ms
memory: 6188kb

input:

100000
54976 44834 98255 10134 69548 72642 83453 24648 82366 68246 95474 47973 78830 84101 33218 73523 14032 65657 11930 2369 99858 907 19743 88151 42335 79337 41632 98570 27562 79154 6994 68363 72170 22241 31557 69573 93312 88572 66407 19749 60550 51901 46654 90766 9248 49164 59843 67740 62362 1674...

output:

41365165572955

result:

ok answer is '41365165572955'

Test #17:

score: 0
Accepted
time: 17ms
memory: 6404kb

input:

100000
52514 59376 65020 46660 28942 70433 37592 10462 81123 1559 28912 73810 48957 55400 46393 56038 49869 47458 57037 23575 12640 81852 94803 11680 56505 37808 72007 56684 51721 8687 18817 80056 19993 64252 13111 55161 33209 91834 45115 95788 56511 85798 33649 56232 22604 72044 7662 18417 87508 44...

output:

99908843100769

result:

ok answer is '99908843100769'

Test #18:

score: 0
Accepted
time: 15ms
memory: 6092kb

input:

100000
65481 51973 37559 62169 88198 55005 82543 39969 55371 92109 80146 27328 32827 53755 90320 96556 6156 12481 27149 60788 57816 49647 37363 16662 37427 61346 67098 57147 21316 15931 10385 95515 97230 58451 53501 40213 86 12073 57178 91352 68755 50878 96733 55941 87092 89181 48874 36839 5196 6158...

output:

23897891819752

result:

ok answer is '23897891819752'

Test #19:

score: 0
Accepted
time: 14ms
memory: 6400kb

input:

100000
30209 26736 54098 60399 47142 23933 92066 72897 32069 57988 375 34666 34975 31707 59934 43164 49966 37413 87539 52921 93557 33039 25459 20478 70013 16777 16443 24365 88788 83754 81240 95863 46242 32370 17349 65476 86515 84735 73774 17895 12795 70981 77649 71668 9721 14888 96207 13836 48479 93...

output:

57044416873160

result:

ok answer is '57044416873160'

Test #20:

score: 0
Accepted
time: 20ms
memory: 6524kb

input:

100000
61017 87302 92522 69165 98144 62345 29014 24727 41625 20245 86362 7585 49422 21106 27598 42013 2189 57984 41583 3397 22274 908 23371 28777 16367 33096 6180 44325 82618 93594 89365 86175 81417 99876 12052 56251 53057 52807 62112 34129 70143 17905 34783 4896 50036 25810 98692 32982 42159 97370 ...

output:

41307183076823

result:

ok answer is '41307183076823'

Test #21:

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

input:

100000
41620 33722 38688 27371 95837 32291 68618 41317 36319 65280 6690 62382 42602 54418 46532 38121 64330 50243 98436 65420 42223 85177 46688 17983 81865 10830 87605 12944 36756 64026 16175 74124 55381 1820 47520 9531 10355 2393 34312 61014 75188 95662 76200 23766 30328 56849 99812 6189 2153 45548...

output:

99992969527355

result:

ok answer is '99992969527355'

Test #22:

score: 0
Accepted
time: 19ms
memory: 4852kb

input:

100000
21437 44301 91174 64507 2257 81025 52338 54639 5742 92225 37814 96991 33764 8787 71765 23963 49406 87629 94472 72941 17108 45204 67766 80763 3946 86011 64192 38549 93117 34002 97715 66759 83546 70832 18033 21768 23837 16867 68088 93093 49258 98353 60732 75400 68805 6214 55951 38603 99344 5673...

output:

23811584803778

result:

ok answer is '23811584803778'

Test #23:

score: 0
Accepted
time: 17ms
memory: 4888kb

input:

100000
41708 13330 60998 38728 28443 19025 86297 91951 23917 3861 41622 35302 53873 47517 15229 69388 60925 61402 67852 42226 11100 41717 61271 20735 21553 32291 68510 27574 51424 71884 94080 45896 78931 32389 10719 26232 19298 99826 58053 62162 76956 80966 14407 51349 82379 51787 8916 28097 22627 2...

output:

65894527778867

result:

ok answer is '65894527778867'

Test #24:

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

input:

100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

0

result:

ok answer is '0'

Test #25:

score: 0
Accepted
time: 18ms
memory: 8108kb

input:

100000
26857 22205 49169 68257 72021 59702 39953 67509 16124 19175 75598 40666 48437 98738 30661 51926 99930 50966 43530 35317 14966 86828 49674 60871 84799 71821 55785 64408 54254 86687 57936 32068 4338 14892 6610 96846 51639 17929 66143 2550 25877 42042 73755 98741 45610 61282 37896 49010 18941 44...

output:

41394241651451

result:

ok answer is '41394241651451'

Test #26:

score: 0
Accepted
time: 17ms
memory: 8084kb

input:

100000
77529 31201 11435 70765 8689 24000 72733 94229 28234 39906 26635 82227 65187 20873 8055 94854 98186 40808 82388 62597 21798 47246 59911 70772 4516 74714 50974 51569 18972 29518 41112 55616 32003 29150 19872 74444 59465 39376 62055 80948 53289 77273 15494 40647 61166 70155 18924 50136 71282 17...

output:

99999500482417

result:

ok answer is '99999500482417'

Test #27:

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

input:

100000
82787 7687 19112 23952 27550 39801 31722 17401 33943 2214 41158 50012 62111 76778 46725 71320 98745 53378 84169 68838 82817 92624 82206 64906 88154 36628 93186 66024 46485 36522 49520 69611 27072 65068 28588 83933 91761 85073 13475 47889 80668 21248 64829 25812 41758 67389 97480 56693 28218 3...

output:

23859535254372

result:

ok answer is '23859535254372'

Test #28:

score: 0
Accepted
time: 18ms
memory: 8200kb

input:

100000
55383 54829 42353 58540 65644 57612 263 3533 61625 58070 55826 54812 911 92035 69889 72315 55021 33985 11913 79072 92160 54699 61199 6749 39734 75778 63219 18313 75776 70189 77909 89791 71415 59831 60309 13355 23457 10292 40601 38991 75624 61532 49134 53123 74175 89478 42180 47034 24546 33414...

output:

99999499356395

result:

ok answer is '99999499356395'