QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#886582#10067. CheeseAdamGS#0 29ms73444kbC++231.2kb2025-02-07 09:43:362025-02-07 09:43:38

Judging History

This is the latest submission verdict.

  • [2025-02-07 09:43:38]
  • Judged
  • Verdict: 0
  • Time: 29ms
  • Memory: 73444kb
Show
  • [2025-02-07 09:43:36]
  • 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+1) if(!chk(i, j, a, p)) ok=false;
		if(!ok) {
			cout << 0 << '\n';
			continue;
		}
		cout << 1 << '\n';
		rep(p, k+1) uni(i, j, a, p);
	}
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 73444kb

input:

10 10
5 3 0 4
6 8 1 4
9 2 0 128
7 8 6 4096
9 6 7 256
2 5 1 8
10 6 7 128
9 1 9 32
9 3 2 2
9 3 1 256

output:

1
1
1
1
1
1
1
1
0
0

result:

wrong answer 10th lines differ - expected: '1', found: '0'

Subtask #2:

score: 0
Wrong Answer

Test #7:

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

input:

2 3
2 1 1 2
2 1 1 2
2 1 9 2

output:

1
1
1

result:

ok 3 lines

Test #8:

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

input:

2 10
1 2 0 2
1 2 93 2
1 2 93 2
1 2 0 2
1 2 5 2
1 2 29 2
1 2 19 2
1 2 0 2
1 2 23 2
1 2 0 2

output:

1
0
0
1
0
0
0
1
0
1

result:

ok 10 lines

Test #9:

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

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:

1
1
1
1
1
1
1
1
1
1

result:

ok 10 lines

Test #10:

score: 0
Wrong Answer
time: 0ms
memory: 73312kb

input:

10 10
3 4 1 2
1 8 1 2
2 5 1 2
4 5 1 2
3 4 1 2
4 8 1 2
3 10 0 2
8 10 1 2
1 4 0 2
2 8 1 2

output:

1
1
1
1
1
1
1
0
0
1

result:

wrong answer 9th lines differ - expected: '1', found: '0'

Subtask #3:

score: 0
Time Limit Exceeded

Test #15:

score: 11
Accepted
time: 1ms
memory: 73316kb

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:

1
1
1
1
1
1
1
1
0
0
1
0
1
0
1
1
1
0
0
1
1
1
1
0
1
0
1
1
1
0
0
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
1
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
1
1
1
1
0
1
0
0
0
1
1
1
1
1
1
1
0
0

result:

ok 100 lines

Test #16:

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

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:

1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
0
0
0
0
1
0
0
0
1
1
0
1
1
0
1
1
1
0
1
1
1
0
0
1
1
0
1
0
1
1
1
1
0
0
0
0
0
1
0
0
0
1
1
0
1
0
1
0
1
0
0
0
1
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
1
1
1
0
0
1
1
1

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:

1
1
1
1
1
1
1
1
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
0
0
1
0
1
1
0
0
1
1
0
1
1
0
0
1
1
0
1
0
1
1
0
0
1
0
1
1
1
1
1
1
1
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
1
0
1
1
0
0
1
1
0
0
0
1
1
0
1
1
1
0
1
0
1
1
0
1
1

result:

ok 100 lines

Test #18:

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

input:

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

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0

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:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

Subtask #4:

score: 0
Wrong Answer

Test #23:

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

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:

1
1
1
1
1
1
1
1
1
1

result:

ok 10 lines

Test #24:

score: 0
Wrong Answer
time: 29ms
memory: 73440kb

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:

1
1
1
1
1
1
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
...

result:

wrong answer 7th lines differ - expected: '1', found: '0'

Subtask #5:

score: 0
Wrong Answer

Test #27:

score: 0
Wrong Answer
time: 0ms
memory: 73316kb

input:

3 500
1 2 12 32
1 3 7 32
1 3 6 32
1 2 40 2
3 2 69 32
3 2 5 16
1 3 7 16
1 2 4 8
3 2 5 16
1 2 13 4
1 2 0 4
3 2 5 32
1 2 12 16
1 2 12 32
1 3 99 2
3 2 5 32
1 2 4 8
1 2 60 32
1 2 12 32
1 3 40 4
1 2 4 8
1 2 4 8
3 2 5 32
1 3 91 4
1 3 96 2
1 3 3 4
3 2 5 8
1 2 11 32
3 2 1 2
3 2 61 32
1 3 7 8
1 2 76 16
1 3 22...

output:

1
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
1
0
0
0
0
0
0
0
1
0
0
1
1
1
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
1
1
0
0
1
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
...

result:

wrong answer 4th lines differ - expected: '1', found: '0'

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:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:
English 繁體中文 简体中文

Server Time: 2025-02-14 06:54:40 | OpenSource Project