QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#886587	#10067. Cheese	AdamGS^#	26	241ms	181132kb	C++23	1.2kb	2025-02-07 09:46:48	2025-02-07 09:46:49

Judging History

This is the latest submission verdict.

[2025-02-07 09:46:49]
Judged

Verdict: 26
Time: 241ms
Memory: 181132kb

Show

[2025-02-07 09:46:48]
Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7, LG=35;
pair<ll,ll>F[LG][LIM];
ll mod(ll x, ll k) {
	return ((x%k)+k)%k;
}
pair<ll,ll>fnd(ll k, ll x) {
	if(F[k][x].st==x) return {x, 0};
	pair<ll,ll>p=fnd(k, F[k][x].st);
	F[k][x]={p.st, p.nd+F[k][x].nd};
	return F[k][x];
}
bool chk(ll a, ll b, ll c, ll k) {
	pair<ll,ll>x=fnd(k, a), y=fnd(k, b);
	if(x.st!=y.st) return true;
	return mod(-x.nd+y.nd+c, 1ll<<(k+1))==0;
}
void uni(ll a, ll b, ll c, ll k) {
	pair<ll,ll>x=fnd(k, a), y=fnd(k, b);
	if(x.st==y.st) return;
	ll z=mod(-x.nd+y.nd+c, 1ll<<(k+1));
	F[k][x.st]={y.st, z};
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	rep(i, LG) rep(j, n) F[i][j]={j, 0};
	while(m--) {
		ll i, j, a, b;
		cin >> i >> j >> a >> b; --i; --j;
		ll k=0;
		while(k+1<LG && (1ll<<k)!=b) ++k;
		if(b!=-1) a+=1ll<<k;
		bool ok=true;
		rep(p, k) if(!chk(i, j, a, p)) ok=false;
		if(!ok) {
			cout << 0 << '\n';
			continue;
		}
		cout << 1 << '\n';
		rep(p, k) uni(i, j, a, p);
	}
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7

Accepted

Test #1:

score: 7

Accepted

time: 0ms

memory: 73312kb

input:

output:

result:

ok 10 lines

Test #2:

score: 7

Accepted

time: 1ms

memory: 73396kb

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

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

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

memory: 73444kb

input:

output:

1
1
1

result:

ok 3 lines

Test #6:

score: 7

Accepted

time: 0ms

memory: 73440kb

input:

output:

result:

ok 10 lines

Subtask #2:

score: 0

Memory Limit Exceeded

Test #7:

score: 8

Accepted

time: 0ms

memory: 73316kb

input:

output:

1
1
1

result:

ok 3 lines

Test #8:

score: 8

Accepted

time: 0ms

memory: 73316kb

input:

output:

result:

ok 10 lines

Test #9:

score: 8

Accepted

time: 0ms

memory: 73316kb

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

input:

output:

result:

ok 10 lines

Test #11:

score: 8

Accepted

time: 88ms

memory: 73312kb

input:

output:

result:

ok 500000 lines

Test #12:

score: 8

Accepted

time: 89ms

memory: 73444kb

input:

output:

result:

ok 500000 lines

Test #13:

score: 0

Memory Limit Exceeded

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:

Subtask #3:

score: 0

Time Limit Exceeded

Test #15:

score: 11

Accepted

time: 0ms

memory: 73436kb

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

memory: 73316kb

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

memory: 73312kb

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

input:

output:

result:

ok 100 lines

Test #19:

score: 0

Time Limit Exceeded

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:

Subtask #4:

score: 19

Accepted

Test #23:

score: 19

Accepted

time: 0ms

memory: 73440kb

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

memory: 73444kb

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

memory: 73316kb

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

memory: 73316kb

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

Memory Limit Exceeded

Test #27:

score: 38

Accepted

time: 0ms

memory: 73444kb

input:

output:

result:

ok 500 lines

Test #28:

score: 38

Accepted

time: 241ms

memory: 181132kb

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

Memory Limit Exceeded

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:

Subtask #6:

score: 0

Memory Limit Exceeded

Test #35:

score: 0

Memory Limit Exceeded

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: