QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #886577 | #10067. Cheese | AdamGS# | 0 | 1ms | 73440kb | C++23 | 1.2kb | 2025-02-07 09:33:53 | 2025-02-07 09:33:54 |
Judging History
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) {
x%=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.st+y.st+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);
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 73312kb
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 1 0
result:
wrong answer 9th lines differ - expected: '0', found: '1'
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 73316kb
input:
2 3 2 1 1 2 2 1 1 2 2 1 9 2
output:
1 0 0
result:
wrong answer 2nd lines differ - expected: '1', found: '0'
Subtask #3:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 1ms
memory: 73440kb
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 0 1 1 0 0 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 6th lines differ - expected: '1', found: '0'
Subtask #4:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 0ms
memory: 73308kb
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 0 1 0 1 1 1
result:
wrong answer 5th lines differ - expected: '1', found: '0'
Subtask #5:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 0ms
memory: 73268kb
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 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 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 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 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 1 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 ...