QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#884165	#10067. Cheese	guleng2007^#	100 ✓	1148ms	141008kb	C++20	1.3kb	2025-02-05 21:42:55	2025-02-05 21:42:55

Judging History

This is the latest submission verdict.

[2025-02-05 21:42:55]
Judged

Verdict: 100
Time: 1148ms
Memory: 141008kb

Show

[2025-02-05 21:42:55]
Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=5e5+5;

int LG2[(1<<16)+5], n;

struct BCJ
{
	int fa[N], val[N], Base;

	void init()
	{
		for(int i=1;i<=n;i++)
			fa[i]=i, val[i]=0;
	}

	int getfa(int x)
	{
		if(x!=fa[x])
		{
			int p=fa[x];
			fa[x]=getfa(fa[x]);
			(val[x] += val[p]) %= Base;
		}
		return fa[x];
	}

	bool check(int x,int y,int z)
	{
		z=(z%Base+Base)%Base;
		int fax=getfa(x), fay=getfa(y);
		if(fax==fay)
		{
			if((val[x]-val[y]+Base)%Base!=z)
				return false;
			return true;
		}
		return true;
	}

	void merge(int x,int y,int z)
	{
		z=(z%Base+Base)%Base;
		int fax=getfa(x), fay=getfa(y);
		if(fax!=fay)
		{
			fa[fax]=fay;
			val[fax]=(val[y]-val[x]+z+Base)%Base;
			getfa(x), getfa(y);
		}
	}
} U[20];

signed main()
{
	int m;
	cin >> n >> m;
	for(int i=0;i<=16;i++)
		U[i].Base=1<<i;
	U[16].Base=1e18;

	for(int i=0;i<=16;i++)
		U[i].init(), LG2[1<<i]=i;

	for(int i=1;i<=m;i++)
	{
		int x,y,z,v,typ;
		scanf("%lld %lld %lld %lld",&x,&y,&z,&v);
		if(v==-1)
			typ=16;
		else
			typ=LG2[v];

		bool can=true;
		for(int i=1;i<=typ;i++)
			if(!U[i].check(x,y,z))
			{
				can=false;
				break;
			}

		printf("%d\n",can);
		if(can)
		{
			for(int i=1;i<=typ;i++)
				U[i].merge(x,y,z);
		}
	}
	return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7

Accepted

Test #1:

score: 7

Accepted

time: 0ms

memory: 73452kb

input:

output:

result:

ok 10 lines

Test #2:

score: 7

Accepted

time: 0ms

memory: 73576kb

input:

10 10
2 7 40 64
6 1 2249 8192
7 3 16515 -1
7 10 173 512
5 4 12 4096
5 4 12 128
2 5 1622 16384
4 3 9 128
6 1 10441 -1
1 4 178 256

output:

result:

ok 10 lines

Test #3:

score: 7

Accepted

time: 0ms

memory: 75608kb

input:

10 10
1 2 32768 -1
5 4 32768 -1
2 3 32768 -1
6 5 32768 -1
3 4 0 -1
1 5 32768 -1
1 5 32768 -1
2 4 32768 -1
2 4 32768 -1
1 5 32768 -1

output:

result:

ok 10 lines

Test #4:

score: 7

Accepted

time: 0ms

memory: 73580kb

input:

10 10
7 9 2 1024
1 7 6 512
8 10 2 4096
1 8 7 16384
1 7 6 64
6 9 4 1024
8 9 2 32
2 9 8 128
1 10 10 4096
6 7 2 4

output:

result:

ok 10 lines

Test #5:

score: 7

Accepted

time: 0ms

memory: 75596kb

input:

output:

1
1
1

result:

ok 3 lines

Test #6:

score: 7

Accepted

time: 0ms

memory: 73580kb

input:

output:

result:

ok 10 lines

Subtask #2:

score: 8

Accepted

Test #7:

score: 8

Accepted

time: 0ms

memory: 73452kb

input:

output:

1
1
1

result:

ok 3 lines

Test #8:

score: 8

Accepted

time: 0ms

memory: 75596kb

input:

output:

result:

ok 10 lines

Test #9:

score: 8

Accepted

time: 0ms

memory: 73580kb

input:

10 10
8 10 0 2
7 2 1 2
1 6 1 2
1 6 1 2
10 4 0 2
8 5 1 2
5 2 0 2
7 8 0 2
7 10 12234 2
1 4 0 2

output:

result:

ok 10 lines

Test #10:

score: 8

Accepted

time: 0ms

memory: 75596kb

input:

output:

result:

ok 10 lines

Test #11:

score: 8

Accepted

time: 98ms

memory: 73580kb

input:

output:

result:

ok 500000 lines

Test #12:

score: 8

Accepted

time: 97ms

memory: 73372kb

input:

output:

result:

ok 500000 lines

Test #13:

score: 8

Accepted

time: 175ms

memory: 136888kb

input:

500000 500000
357964 438154 1 2
41827 118145 1 2
303056 312211 0 2
66489 433252 1 2
476108 487095 0 2
481550 297953 1 2
353414 252330 1 2
33824 467092 0 2
243604 44883 0 2
284639 283020 1 2
332764 417453 1 2
193372 39008 1 2
239157 28915 1 2
430016 77427 0 2
97924 269527 0 2
6933 301951 1 2
314869 2...

output:

result:

ok 500000 lines

Test #14:

score: 8

Accepted

time: 176ms

memory: 136908kb

input:

500000 500000
42242 200698 0 2
324887 353798 1 2
269345 382965 0 2
40196 409688 0 2
249997 260289 0 2
28596 275864 0 2
327149 339725 0 2
213145 335625 0 2
176735 354803 0 2
301996 317917 1 2
395016 498137 1 2
280194 288375 1 2
124111 466990 1 2
66211 131133 0 2
403681 448180 1 2
75517 130785 0 2
598...

output:

result:

ok 500000 lines

Subtask #3:

score: 11

Accepted

Test #15:

score: 11

Accepted

time: 0ms

memory: 73576kb

input:

10 100
7 3 27490 -1
4 3 12572 -1
10 2 26036 -1
7 1 21174 -1
7 10 576 -1
4 3 12572 -1
7 6 798 -1
6 8 20930 -1
7 8 14464 -1
6 4 20671 -1
4 3 12572 -1
4 2 11764 -1
1 3 6316 -1
1 8 16743 -1
9 3 6305 -1
10 9 20609 -1
1 8 554 -1
6 4 13117 -1
1 8 20767 -1
7 6 798 -1
10 6 222 -1
4 3 12572 -1
5 4 11211 -1
7 ...

output:

result:

ok 100 lines

Test #16:

score: 11

Accepted

time: 0ms

memory: 73408kb

input:

10 100
10 4 6526 -1
5 10 576 -1
5 7 3541 -1
3 10 11464 -1
7 4 3561 -1
1 7 12988 -1
3 7 14429 -1
2 9 9756 -1
3 4 13768 -1
3 6 17186 -1
2 7 14184 -1
8 4 2688 -1
7 4 3561 -1
5 7 3541 -1
9 10 20308 -1
9 10 5245 -1
9 5 10654 -1
5 7 3541 -1
2 4 17745 -1
5 4 7102 -1
3 6 17186 -1
10 4 6526 -1
5 7 3541 -1
8 ...

output:

result:

ok 100 lines

Test #17:

score: 11

Accepted

time: 1ms

memory: 73584kb

input:

10 100
1 2 32768 -1
7 6 32768 -1
2 3 32768 -1
8 7 32768 -1
3 4 32768 -1
9 8 32768 -1
4 5 32768 -1
10 9 32768 -1
5 6 0 -1
4 6 32768 -1
3 8 0 -1
4 7 32768 -1
4 2 32768 -1
8 7 0 -1
3 7 32768 -1
1 9 32768 -1
1 10 0 -1
10 4 32768 -1
4 8 0 -1
4 7 32768 -1
1 9 32768 -1
1 10 0 -1
3 7 32768 -1
8 2 0 -1
5 2 3...

output:

result:

ok 100 lines

Test #18:

score: 11

Accepted

time: 0ms

memory: 73584kb

input:

output:

result:

ok 100 lines

Test #19:

score: 11

Accepted

time: 1146ms

memory: 138528kb

input:

500000 500000
13873 279891 11573 -1
315715 77632 3454 -1
63906 170183 19387 -1
169363 18368 27472 -1
299561 298050 15989 -1
359385 325049 4908 -1
40943 156655 1577 -1
66910 435658 24450 -1
399132 379866 6084 -1
66289 18779 562 -1
70134 4045 1344 -1
90618 138901 2029 -1
288301 83003 14662 -1
238820 4...

output:

result:

ok 500000 lines

Test #20:

score: 11

Accepted

time: 1109ms

memory: 137572kb

input:

500000 500000
16284 381782 2569 -1
311055 12198 8879 -1
435452 425455 2627 -1
4208 86092 23897 -1
445986 434582 3073 -1
157175 39248 2353 -1
252921 119247 10324 -1
6671 150463 2531 -1
121540 230431 14089 -1
344154 89016 11502 -1
253327 237783 8109 -1
253544 483684 13845 -1
466525 12716 6946 -1
12182...

output:

result:

ok 500000 lines

Test #21:

score: 11

Accepted

time: 382ms

memory: 141008kb

input:

500000 500000
1 2 32768 -1
166668 166667 32768 -1
2 3 32768 -1
166669 166668 32768 -1
3 4 32768 -1
166670 166669 32768 -1
4 5 32768 -1
166671 166670 32768 -1
5 6 32768 -1
166672 166671 32768 -1
6 7 32768 -1
166673 166672 32768 -1
7 8 32768 -1
166674 166673 32768 -1
8 9 32768 -1
166675 166674 32768 -...

output:

result:

ok 500000 lines

Test #22:

score: 11

Accepted

time: 1148ms

memory: 138092kb

input:

500000 500000
32162 159564 29098 -1
341460 380982 6754 -1
64389 463165 5560 -1
223970 283907 27169 -1
162394 383000 23998 -1
18269 374513 28564 -1
230239 296395 620 -1
63374 252482 25268 -1
309374 479733 6519 -1
95844 414818 24062 -1
314312 342142 27830 -1
95438 406926 16576 -1
128944 349090 23538 -...

output:

result:

ok 500000 lines

Subtask #4:

score: 19

Accepted

Test #23:

score: 19

Accepted

time: 0ms

memory: 73524kb

input:

10 10
4 9 5 8
10 7 4894 8192
4 3 10 32
4 5 14 32
5 3 6972 32768
2 5 173 1024
4 5 1134 -1
6 9 22 64
8 3 307 512
1 5 16 64

output:

result:

ok 10 lines

Test #24:

score: 19

Accepted

time: 29ms

memory: 75608kb

input:

10 100000
3 7 0 2048
6 2 0 4096
3 10 1 128
5 9 0 4
10 2 2 1024
3 1 2 4
2 6 0 1024
6 2 0 4096
10 4 1 32768
8 10 1 4096
8 1 2 32768
7 9 2 4096
3 1 1 32
3 1 2 1024
7 9 2 32768
3 7 0 -1
7 5 2 8192
10 2 2 16384
10 4 2 4096
1 9 0 16384
3 7 0 256
5 1 0 1024
8 6 3 256
10 1 1 4096
7 2 0 2
8 1 0 2
2 6 0 32
3 ...

output:

result:

ok 100000 lines

Test #25:

score: 19

Accepted

time: 150ms

memory: 73576kb

input:

10 500000
3 8 6196 -1
9 6 1 2
10 1 1 2
9 5 644 1024
10 1 649 2048
4 7 7 8
3 8 6936 4096
4 7 2271 8192
2 6 0 2
2 8 3 4
1 9 77 128
10 8 56 64
10 3 68 256
2 9 337 1024
7 9 1 32
2 5 981 2048
3 2 1089 32768
2 8 3 8
10 4 2678 32768
1 6 12028 2
7 8 6435 16384
10 5 11135 4
4 1 3 4
8 9 4639 16
4 1 18748 8
7 ...

output:

result:

ok 500000 lines

Test #26:

score: 19

Accepted

time: 171ms

memory: 73580kb

input:

10 500000
4 5 1 16384
1 4 3 16
8 9 1 128
4 10 6 16
4 7 3 64
5 6 1 4
8 9 1 16384
4 6 2 -1
5 10 5 8
7 9 2 8
1 4 3 512
3 4 1 8192
2 3 1 16384
3 10 3 4
9 10 1 8
5 7 2 64
6 7 1 16384
2 6 4 4096
9 10 1 4
1 9 8 16
6 10 0 2
1 9 8 32768
3 10 7 256
3 7 0 2
3 5 2 512
5 9 4 32
3 9 6 1024
5 7 2 8192
4 10 6 4096
...

output:

result:

ok 500000 lines

Subtask #5:

score: 38

Accepted

Test #27:

score: 38

Accepted

time: 1ms

memory: 73452kb

input:

output:

result:

ok 500 lines

Test #28:

score: 38

Accepted

time: 254ms

memory: 124164kb

input:

200000 500000
54908 145605 7 32
189491 97533 1 2
194568 88722 1 8
110649 31531 15 16
129699 20484 0 32
106094 91088 14 16
92050 107767 7 16
136616 58686 19 32
98581 154024 13 16
84819 101604 0 2
140703 88356 1 2
62318 146749 28 32
37421 72051 2 8
61718 51259 3 8
20824 55091 0 2
42816 174547 0 2
4994...

output:

result:

ok 500000 lines

Test #29:

score: 38

Accepted

time: 262ms

memory: 136892kb

input:

500000 500000
317625 208495 1 32
413826 182142 7 16
232417 470434 1 8
230680 214033 16 32
63783 124684 8 16
461348 122690 28 32
495407 466737 1 2
99973 87471 5 16
115692 94361 0 2
345336 285687 1 4
445530 418163 0 2
344737 322205 0 2
374116 27506 3 32
312529 292726 31 32
482073 282088 3 4
142761 259...

output:

result:

ok 500000 lines

Test #30:

score: 38

Accepted

time: 257ms

memory: 136848kb

input:

500000 500000
72816 367942 6 8
267288 323344 0 4
318777 404801 0 4
128519 275466 3 4
437496 471749 13 32
70670 419125 7 32
38161 497727 0 2
67864 261402 2 16
16130 102771 1 8
75831 218173 2 4
355483 440652 1 2
39592 288690 10 32
401811 479656 1 2
35343 368980 5 16
158136 229510 0 2
222100 273142 0 2...

output:

result:

ok 500000 lines

Test #31:

score: 38

Accepted

time: 0ms

memory: 73584kb

input:

10 100
2 7 1 2
8 9 2 4
8 9 29661 4
8 1 0 4
2 3 1 2
9 10 0 2
5 6 0 4
2 10 3 4
8 1 7954 4
9 1 2 4
4 7 1 2
8 3 2 4
4 6 1 2
9 3 0 2
4 3 3 4
3 1 2 4
5 4 3 4
3 1 0 2
1 10 26446 2
7 10 0 2
4 6 1 4
8 6 0 4
4 7 28838 2
9 1 0 2
8 3 0 2
2 1 3 4
2 8 1 2
5 4 1 2
9 5 19506 4
5 7 0 4
3 1 17786 4
5 3 5808 2
8 5 0 2...

output:

result:

ok 100 lines

Test #32:

score: 38

Accepted

time: 106ms

memory: 73580kb

input:

output:

result:

ok 500000 lines

Test #33:

score: 38

Accepted

time: 192ms

memory: 138528kb

input:

500000 500000
160750 160633 0 2
351051 413501 0 4
51603 172545 1 4
247970 392536 3 4
431471 490763 0 2
378771 371791 3 4
285432 460552 1 2
376745 348158 2 4
476546 306901 0 4
151356 80759 3 4
84532 166831 1 2
425602 135140 1 4
82739 250636 1 2
210983 53629 0 2
210740 210695 2 4
233855 45913 2 4
3754...

output:

result:

ok 500000 lines

Test #34:

score: 38

Accepted

time: 189ms

memory: 136860kb

input:

500000 500000
203297 495396 3 4
23578 380815 1 4
260004 421621 1 4
357467 489634 3 4
380673 496871 0 2
261055 305109 0 2
269953 363773 0 4
285999 486884 1 2
75317 104777 0 4
143666 302503 1 4
18273 301407 2 4
339705 482372 1 2
106408 106814 0 2
47221 137923 0 2
193092 307172 0 2
227022 241264 2 4
27...

output:

result:

ok 500000 lines

Subtask #6:

score: 17

Accepted

Test #35:

score: 17

Accepted

time: 579ms

memory: 137592kb

input:

500000 500000
14167 287469 6 512
104859 279213 2 2048
230903 352549 2 16384
20412 206001 2 64
31177 491167 4 16384
374670 2710 7 1024
463688 378992 3 2048
239144 207425 4 16384
407488 243971 0 2
278719 34617 9 256
155441 483962 1 16
263008 53859 0 8192
397627 240244 4 8
387592 488780 2 16384
224109 ...

output:

result:

ok 500000 lines

Test #36:

score: 17

Accepted

time: 557ms

memory: 137216kb

input:

500000 500000
244153 243508 0 2
313268 176599 493 512
83585 496063 12340 32768
277264 188013 242 256
184698 192558 15 16
4966 440986 7 16
424517 25771 0 2
160664 368886 15287 32768
237474 320510 0 4
81504 130148 249 1024
487635 342120 484 512
398356 268088 60 64
392658 314852 1 16
74888 447885 8600 ...

output:

result:

ok 500000 lines

Test #37:

score: 17

Accepted

time: 378ms

memory: 139432kb

input:

500000 500000
1 2 32768 -1
166668 166667 32768 -1
2 3 32768 -1
166669 166668 32768 -1
3 4 32768 -1
166670 166669 32768 -1
4 5 32768 -1
166671 166670 32768 -1
5 6 32768 -1
166672 166671 32768 -1
6 7 32768 -1
166673 166672 32768 -1
7 8 32768 -1
166674 166673 32768 -1
8 9 32768 -1
166675 166674 32768 -...

output:

result:

ok 500000 lines

Test #38:

score: 17

Accepted

time: 541ms

memory: 139836kb

input:

500000 500000
87015 301509 94 128
49207 435186 11 16
341041 475222 37 512
197751 450699 20 512
46115 449553 10222 32768
1573 362051 30 32
93584 188286 494 4096
16751 439757 29790 -1
376384 491774 62 64
266778 328591 4469 8192
637 498367 2 8
109264 464094 14 128
59155 330639 1148 2048
98910 117412 21...

output:

result:

ok 500000 lines

Test #39:

score: 17

Accepted

time: 1145ms

memory: 138504kb

input:

500000 500000
32162 159564 29098 -1
341460 380982 6754 -1
64389 463165 5560 -1
223970 283907 27169 -1
162394 383000 23998 -1
18269 374513 28564 -1
230239 296395 620 -1
63374 252482 25268 -1
309374 479733 6519 -1
95844 414818 24062 -1
314312 342142 27830 -1
95438 406926 16576 -1
128944 349090 23538 -...

output:

result:

ok 500000 lines