QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#556879	#8671. 分流器	jiamengtong	100 ✓	168ms	316432kb	C++14	1.0kb	2024-09-10 21:50:27	2024-09-10 21:50:28

Judging History

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

[2024-09-10 21:50:28]
评测

测评结果：100
用时：168ms
内存：316432kb

查看

[2024-09-10 21:50:27]
提交

answer

#include<bits/stdc++.h>
#define M 50005
using namespace std;
using ull = unsigned long long;
int n, ans[M];
ull hp[M][800];
void add(int x, int y)
{
	for(int i = 0; i <= n / 63; i++)
	{
		hp[y][i] += (hp[x][i] >> 1);
		if(hp[x][i + 1] & 1) hp[y][i] += (1ull << 62);
		if(hp[y][i] >> 63) hp[y][i + 1]++, hp[y][i] ^= (1ull << 63);
	}
}
int ctz(int i)
{
	for(int j = 0; j <= n / 63; j++) if(hp[i][j]) return j * 63 + __builtin_ctzll(hp[i][j]);
}
int main()
{
	scanf("%d", &n);
	hp[1][n / 63] = 1ull << (n % 63);
	int minn = n;
	for(int i = 1, x; i <= n; i++)
	{
		scanf("%d", &x), add(i, x);
		scanf("%d", &x), add(i, x);
		minn = min(minn, ctz(i));
	}
	int pw = n - minn + 1;
	ans[0] = 1;
	int tot = 1;
	while(pw)
	{
		int nt = min(pw, 25);
		pw -= nt;
		for(int i = 0; i < tot; i++) ans[i] <<= nt;
		for(int i = 0; i < tot; i++) ans[i + 1] += ans[i] / 10, ans[i] %= 10;
		while(ans[tot]) ans[tot + 1] += ans[tot] / 10, ans[tot] %= 10, tot++;
	}
	for(int i = tot - 1; i >= 0; i--) printf("%d", ans[i]);
	return 0;
}

源文件, 语言: C++14

这程序好像有点Bug，我给组数据试试？

詳細信息

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 0ms

memory: 3860kb

input:

output:

result:

ok single line: '8'

Test #2:

score: 5

Accepted

time: 0ms

memory: 3740kb

input:

output:

result:

ok single line: '4'

Test #3:

score: 5

Accepted

time: 0ms

memory: 3740kb

input:

output:

result:

ok single line: '8'

Test #4:

score: 5

Accepted

time: 0ms

memory: 3988kb

input:

output:

result:

ok single line: '8'

Test #5:

score: 5

Accepted

time: 0ms

memory: 3980kb

input:

output:

result:

ok single line: '8'

Subtask #2:

score: 15

Accepted

Dependency #1:

100%

Accepted

Test #6:

score: 15

Accepted

time: 0ms

memory: 3856kb

input:

20
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
18 19
20 21
12 19
21 21
15 16
18 18
21 21
19 21
18 21
21 19
20 20
21 21
1 0 0 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1

output:

result:

ok single line: '128'

Test #7:

score: 15

Accepted

time: 0ms

memory: 4036kb

input:

20
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
18 19
20 21
19 15
21 21
21 20
21 19
21 17
21 20
18 21
20 20
21 21
21 21
1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 0

output:

result:

ok single line: '128'

Test #8:

score: 15

Accepted

time: 0ms

memory: 4040kb

input:

20
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
18 19
20 21
21 16
19 13
19 17
20 17
17 20
21 21
20 18
19 21
20 21
21 21
1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0

output:

result:

ok single line: '512'

Test #9:

score: 15

Accepted

time: 0ms

memory: 3864kb

input:

20
2 3
4 5
6 7
8 9
10 11
12 13
14 15
16 17
18 19
20 21
21 18
18 21
19 15
21 20
21 17
20 21
18 19
21 21
20 21
21 21
1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 0

output:

result:

ok single line: '256'

Subtask #3:

score: 15

Accepted

Test #10:

score: 15

Accepted

time: 115ms

memory: 316424kb

input:

50000
2 3
4 5
50001 6
7 8
9 10
11 50001
12 13
14 15
50001 50001
50001 50001
16 50001
50001 50001
17 18
19 20
50001 21
50001 22
50001 50001
23 50001
24 25
26 27
28 29
30 31
50001 50001
32 33
34 50001
50001 35
36 37
38 50001
50001 39
50001 50001
40 41
50001 50001
42 50001
50001 50001
50001 43
50001 44...

output:

8589934592

result:

ok single line: '8589934592'

Test #11:

score: 15

Accepted

time: 135ms

memory: 316428kb

input:

50000
2 3
50001 4
50001 50001
5 50001
6 7
50001 8
9 10
11 12
13 14
15 16
17 18
50001 19
20 21
22 23
50001 24
50001 50001
50001 25
50001 26
50001 27
28 50001
29 30
31 50001
50001 32
33 34
50001 50001
35 36
50001 37
50001 38
39 50001
40 41
42 43
50001 44
45 50001
46 47
48 50001
50001 49
50 50001
51 52...

output:

34359738368

result:

ok single line: '34359738368'

Test #12:

score: 15

Accepted

time: 128ms

memory: 316412kb

input:

50000
2 3
4 5
50001 6
50001 50001
50001 50001
7 8
9 50001
10 11
12 50001
13 50001
50001 14
15 16
17 50001
18 19
50001 20
21 22
23 24
25 26
27 28
29 30
50001 50001
50001 31
50001 32
33 34
50001 50001
50001 35
50001 36
37 38
39 40
41 42
50001 43
44 45
46 50001
47 50001
50001 50001
50001 48
50001 49
50...

output:

8589934592

result:

ok single line: '8589934592'

Subtask #4:

score: 20

Accepted

Dependency #2:

100%

Accepted

Test #13:

score: 20

Accepted

time: 1ms

memory: 4296kb

input:

output:

result:

ok single line: '32768'

Test #14:

score: 20

Accepted

time: 1ms

memory: 4256kb

input:

output:

result:

ok single line: '32768'

Test #15:

score: 20

Accepted

time: 1ms

memory: 6304kb

input:

output:

result:

ok single line: '65536'

Test #16:

score: 20

Accepted

time: 1ms

memory: 4224kb

input:

output:

result:

ok single line: '4096'

Test #17:

score: 20

Accepted

time: 1ms

memory: 4364kb

input:

output:

result:

ok single line: '16384'

Test #18:

score: 20

Accepted

time: 1ms

memory: 4316kb

input:

output:

result:

ok single line: '2048'

Test #19:

score: 20

Accepted

time: 0ms

memory: 6240kb

input:

output:

result:

ok single line: '32768'

Subtask #5:

score: 20

Accepted

Dependency #4:

100%

Accepted

Test #20:

score: 20

Accepted

time: 5ms

memory: 12432kb

input:

output:

20282409603651670423947251286016

result:

ok single line: '20282409603651670423947251286016'

Test #21:

score: 20

Accepted

time: 5ms

memory: 12276kb

input:

output:

2596148429267413814265248164610048

result:

ok single line: '2596148429267413814265248164610048'

Test #22:

score: 20

Accepted

time: 0ms

memory: 12360kb

input:

output:

1267650600228229401496703205376

result:

ok single line: '1267650600228229401496703205376'

Test #23:

score: 20

Accepted

time: 5ms

memory: 12336kb

input:

output:

2535301200456458802993406410752

result:

ok single line: '2535301200456458802993406410752'

Test #24:

score: 20

Accepted

time: 0ms

memory: 12408kb

input:

output:

9903520314283042199192993792

result:

ok single line: '9903520314283042199192993792'

Test #25:

score: 20

Accepted

time: 5ms

memory: 12424kb

input:

output:

2596148429267413814265248164610048

result:

ok single line: '2596148429267413814265248164610048'

Test #26:

score: 20

Accepted

time: 2ms

memory: 12336kb

input:

output:

2535301200456458802993406410752

result:

ok single line: '2535301200456458802993406410752'

Test #27:

score: 20

Accepted

time: 2ms

memory: 12424kb

input:

output:

162259276829213363391578010288128

result:

ok single line: '162259276829213363391578010288128'

Test #28:

score: 20

Accepted

time: 0ms

memory: 12340kb

input:

output:

81129638414606681695789005144064

result:

ok single line: '81129638414606681695789005144064'

Subtask #6:

score: 20

Accepted

Test #29:

score: 20

Accepted

time: 152ms

memory: 316288kb

input:

output:

317624883870373507138831797099734055743873969948324731607638926709094484242961434875861799369272588648755542418038360833477281684824324490604855548268961204923221725750403452934972636403246568312773419816518854101919362705918837856047439617445015267692027248697240015519360857697395495747870630856046...

result:

ok single line: '317624883870373507138831797099...3514898281882163107621939183616'

Test #30:

score: 20

Accepted

time: 135ms

memory: 316340kb

input:

output:

416317287786575963277009613094563421544610489890668192212764494016144322386934411920489577669292967393696864558171240311655342649932938596325596264227092830516965180375568813830927333986463342018918376821907592448467747085901939154678500055377530411669293955412446433141536663401130224186648993275636...

result:

ok single line: '416317287786575963277009613094...4747602858882842222812674916352'

Test #31:

score: 20

Accepted

time: 144ms

memory: 316432kb

input:

output:

266443064183408616497286152380520589788550713530027643016169276170332366327638023629113329708347499131965993317229593799459419295957080701648381609105339411530857715440364040851793493751336538892107761166020859167019358134977241058994240035441619463468348131463965717210583464576723343479455355696407...

result:

ok single line: '266443064183408616497286152380...3846582968501902260011194646528'

Test #32:

score: 20

Accepted

time: 128ms

memory: 316420kb

input:

output:

248144440523729302452212341484167231049901539022128696568467911491480065814813620996767030757244209881840267514092469401154126316269003508285043397085125941346266973242502697605447372190036381494354234231655354767124502113999092075037062201128918177884396288044718762124500670076090231053023930356286...

result:

ok single line: '248144440523729302452212341484...6902460142827204399278296399872'

Test #33:

score: 20

Accepted

time: 127ms

memory: 316348kb

input:

output:

416317287786575963277009613094563421544610489890668192212764494016144322386934411920489577669292967393696864558171240311655342649932938596325596264227092830516965180375568813830927333986463342018918376821907592448467747085901939154678500055377530411669293955412446433141536663401130224186648993275636...

result:

ok single line: '416317287786575963277009613094...4747602858882842222812674916352'

Test #34:

score: 20

Accepted

time: 108ms

memory: 316404kb

input:

50000
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 38
49 50
51 52
53 54
55 56
57 58
31 59
60 61
62 63
64 58
65 66
67 68
69 70
71 72
73 74
42 75
76 77
78 79
74 80
81 50001
82 83
84 46
62 85
86 87
50001 50001
88 51...

output:

208158643893287981638504806547281710772305244945334096106382247008072161193467205960244788834646483696848432279085620155827671324966469298162798132113546415258482590187784406915463666993231671009459188410953796224233873542950969577339250027688765205834646977706223216570768331700565112093324496637818...

result:

ok single line: '208158643893287981638504806547...2373801429441421111406337458176'

Test #35:

score: 20

Accepted

time: 104ms

memory: 316412kb

input:

output:

635249767740747014277663594199468111487747939896649463215277853418188968485922869751723598738545177297511084836076721666954563369648648981209711096537922409846443451500806905869945272806493136625546839633037708203838725411837675712094879234890030535384054497394480031038721715394790991495741261712092...

result:

ok single line: '635249767740747014277663594199...7029796563764326215243878367232'

Subtask #7:

score: 5

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Test #36:

score: 5

Accepted

time: 168ms

memory: 316284kb

input:

output:

502249939076847322365274589508828161408676805383584178531413871344213148904540016402648876573967425302920188384621103349009310938578719045238648838524146994609246605772593509063470010786259060778882772794968575379291919706534607536480791025304753444288417079647481011580652529533585985746503167431109...

result:

ok single line: '502249939076847322365274589508...2433089638503419886946010267648'

Test #37:

score: 5

Accepted

time: 165ms

memory: 316332kb

input:

50000
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
50001 28
29 30
31 32
33 34
35 36
37 27
32 38
39 29
40 41
39 39
42 43
44 32
45 31
46 47
48 49
50 51
35 45
40 52
53 54
55 38
56 57
57 45
58 59
60 61
50001 50001
50001 62
63 64
50001 65
64 62
66 53
67 56
68 69
70 71
49 72
73 50...

output:

289527377724588021602357123150282418590960058083626293765705385289932677080643516325642216994253380182979885775971846616918446575219800661475102224197896969663131697846171597400727995473492693499572815618365334444076179253528236422077251239432118057566155567669235987146916164773203170427194170210841...

result:

ok single line: '289527377724588021602357123150...7332018824313811454389569716224'

Test #38:

score: 5

Accepted

time: 139ms

memory: 316424kb

input:

50000
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 17
27 28
29 30
50001 19
26 30
30 31
32 33
34 35
36 37
38 39
40 41
42 43
44 45
46 47
48 50001
49 48
50 43
51 47
52 41
50 53
54 55
39 56
57 48
39 47
58 59
50001 50001
60 40
61 62
63 63
64 47
65 66
50001 50001
67 68
58 69
70 71
60...

output:

168527114277582162526876853750018879416724700762207092348081866098761486984232624716615663488775829425419148625789586580893051912553958048505651662241374706886203318046272963635115881609667961892888890357202230047013249279423754442295322217647986287231414792866699855743742178178627026748840097693517...

result:

ok single line: '168527114277582162526876853750...0825067584363977589197096615936'

Test #39:

score: 5

Accepted

time: 124ms

memory: 316424kb

input:

output:

310877654655936111963866340110776870252988962677858841202348329047835081525773164313268852046813421955838276308403665959098242084923061963168682792796706829170163694797565162410051336787571788368904258262879282104352382706634367011344461614734103167314420879896920877525570318738663718537078327524355...

result:

ok single line: '310877654655936111963866340110...6021047459428349393673520152576'

Test #40:

score: 5

Accepted

time: 116ms

memory: 316336kb

input:

output:

269643382844131460043002966000030207066759521219531347756930985758018379174772199546585061582041327080670637801263338529428883060086332877609042659586199531017925308874036741816185410575468739028622224571523568075221198847078007107672515548236778059570263668586719769189987485085803242798144156309628...

result:

ok single line: '269643382844131460043002966000...3201081349823641427153545854976'

Test #41:

score: 5

Accepted

time: 117ms

memory: 316416kb

input:

output:

231621902179670417281885698520225934872768046466901035012564308231946141664514813060513773595402704146383908620777477293534757260175840529180081779358317575730505358276937277920582396378794154799658252494692267555260943402822589137661800991545694446052924454135388789717532931818562536341755336168673...

result:

ok single line: '231621902179670417281885698520...8656150594510491635116557729792'

Test #42:

score: 5

Accepted

time: 150ms

memory: 316284kb

input:

output:

579054755449176043204714246300564837181920116167252587531410770579865354161287032651284433988506760365959771551943693233836893150439601322950204448395793939326263395692343194801455990946985386999145631236730668888152358507056472844154502478864236115132311135338471974293832329546406340854388340421683...

result:

ok single line: '579054755449176043204714246300...4664037648627622908779139432448'

Test #43:

score: 5

Accepted

time: 141ms

memory: 316428kb

input:

output:

118590413915991253648325477642355678654857239791053329926432925814756424532231584286983052080846184522948561213838068374289795717210030350940201871031458598774018743437791886295338186945942607257425025277282440988293603022245165638482842107671395556379097320517319060335376861091104018606978732118360...

result:

ok single line: '118590413915991253648325477642...1949104389371717179677557653504'

Test #44:

score: 5

Accepted

time: 160ms

memory: 316400kb

input:

output:

210658892846977703158596067187523599270905875952758865435102332623451858730290780895769579360969786781773935782236983226116314890692447560632064577801718383607754147557841204543894852012084952366111112946502787558766561599279693052869152772059982859039268491083374819679677722723283783436050122116897...

result:

ok single line: '210658892846977703158596067187...7603133448045497198649637076992'

Test #45:

score: 5

Accepted

time: 132ms

memory: 316428kb

input:

output:

144763688862294010801178561575141209295480029041813146882852692644966338540321758162821108497126690091489942887985923308459223287609900330737551112098948484831565848923085798700363997736746346749786407809182667222038089626764118211038625619716059028783077783834617993573458082386601585213597085105420...

result:

ok single line: '144763688862294010801178561575...3666009412156905727194784858112'

Test #46:

score: 5

Accepted

time: 1ms

memory: 4364kb

input:

output:

17179869184

result:

ok single line: '17179869184'

Extra Test:

score: 0

Extra Test Passed