QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #875441 | #10043. Mod Graph | rotcar07 | AC ✓ | 103ms | 8576kb | C++20 | 1.1kb | 2025-01-29 19:42:24 | 2025-01-29 19:42:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e4+5;
int n,q,m,a[N],B,col[N];
vector<int> e[N];bool f=1;
void dfs(int p,int c){
if(~col[p]){
if(col[p]!=c) f=0;
return;
}col[p]=c;
for(int x:e[p]) dfs(x,c^1);
}
int main(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1,x;i<=n;i++)cin>>x,B=gcd(B,x),col[i]=-1;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,e[u].emplace_back(v),e[v].emplace_back(u);
for(int i=1;i<=n&&f;i++) if(!~col[i]) dfs(i,0);
int w=0;
if(f)
for(int i=1;i<=n;i++){
if(col[i])(w+=a[i])%=B;
else (w-=a[i])%=B;
}
while(q--){
int op,x,y;cin>>op>>x;
if(op==1){
bool sb=1;
if(n==1) sb=(a[1]+1==B);
else if(f){
int ww=(w+B+col[x])%B;
sb=(ww==0||ww==1);
}
puts(sb?"YES":"NO");
}
else{
cin>>y;
if(col[x]) (w+=y-a[x])%=B;
else (w-=y-a[x])%=B;
a[x]=y;
}
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
2 1 4 0 0 3 3 1 2 1 1 2 1 1 1 1 1 2
output:
YES NO YES
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
100 99 20 545176231 2149009 296810352 464294904 517017443 161996875 277531414 227239364 669511769 802762188 72982507 53014228 151954698 803486 7450102 102035596 224137078 59092001 429939358 61593212 125109334 755529743 101606658 282438874 178852420 24856971 174481974 68000852 7807479 203105121 50530...
output:
NO NO YES YES YES NO YES YES
result:
ok 8 token(s): yes count is 5, no count is 3
Test #3:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
100 99 20 336342577 39468089 363971406 252846803 475758534 371077308 44779697 114283328 387639202 176490048 691797700 218742599 55250669 101677476 710976901 290175579 125954990 590690266 295640500 559569481 777772175 91729825 25367669 347238826 97265071 166456655 215699647 252678796 555339722 818759...
output:
YES YES YES YES YES YES YES YES YES YES
result:
ok 10 token(s): yes count is 10, no count is 0
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
100 200 20 376217719 40752341 199958286 733157884 165613590 122258495 16842149 138379722 469440397 205674823 344950589 24835950 7044922 197758921 535437376 2540953 112119947 223063142 44967578 221181144 585079167 393892026 728588471 5881809 193202233 359753346 652786358 282317378 331284029 619260995...
output:
YES NO YES YES YES YES NO YES YES YES
result:
ok 10 token(s): yes count is 8, no count is 2
Test #5:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
100 200 20 370875071 154466455 758306944 64495650 533714565 300239278 99080590 362329958 79378734 103274217 205250835 511582589 345401636 168791237 62615996 282196842 175048464 166208163 421127710 1239481 356604786 202328347 62889425 543321761 399597138 126307432 510390488 29685754 15005612 15951477...
output:
YES YES YES YES YES YES YES YES YES YES YES
result:
ok 11 token(s): yes count is 11, no count is 0
Test #6:
score: 0
Accepted
time: 77ms
memory: 6912kb
input:
50000 49999 50000 1313003 225677075 243833984 92656364 8496173 127233210 632612469 268302322 98198905 12017196 56103451 63363761 256987183 711103762 124543577 683208825 424028511 454228233 283472979 97660573 142447324 138191846 26803549 200796285 1745906 180428555 216748362 188962529 77783071 436816...
output:
YES NO YES YES YES YES YES YES NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO YES YES NO NO NO NO NO YES YES YES YES YES NO YES YES YES NO NO YES YES NO NO NO NO NO YES NO YES NO YES NO YES NO YES YES NO NO NO YES NO YES NO YES YES NO YES YES NO NO NO NO YES YES YES YES NO NO NO NO Y...
result:
ok 24943 token(s): yes count is 8212, no count is 16731
Test #7:
score: 0
Accepted
time: 74ms
memory: 6656kb
input:
49000 50000 50000 392295479 111240864 88210519 70832005 12349711 415946626 13642215 480395172 41598341 777778084 825422622 58038892 92093294 3459406 49370155 369759431 115830106 700886878 137158316 164628037 425317403 276378481 238632126 391330955 825688846 4681221 37785217 819423319 200031046 15809...
output:
NO NO NO NO NO NO YES YES YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO YES YES NO NO NO NO NO YES YES NO NO YES NO NO NO NO NO NO YES YES NO NO YES YES NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES YES YES YES YES YES YES NO NO YES YES NO ...
result:
ok 25028 token(s): yes count is 8266, no count is 16762
Test #8:
score: 0
Accepted
time: 74ms
memory: 6784kb
input:
40000 50000 50000 618113568 82065382 278017986 503862768 242947104 122640417 1385593 690621304 217132331 23835549 602196658 482513168 219004777 53606608 720683008 11566854 101322612 54748616 306031215 4931070 171211893 183291078 27650023 153572569 66550656 286701945 34765062 49150947 2477601 4845806...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 25112 token(s): yes count is 25112, no count is 0
Test #9:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 0 9 0 4 1 1 2 1 1 1 1 2 1 2 1 1 2 1 3 1 1 2 1 0 1 1
output:
NO NO NO YES NO
result:
ok 5 token(s): yes count is 1, no count is 4
Test #10:
score: 0
Accepted
time: 103ms
memory: 8576kb
input:
49000 100000 50000 56160431 315163835 90363679 239601578 116443922 42519557 18444743 351013734 19454014 139947294 702316474 450765006 112525488 180728004 3444274 150116062 300825504 296649425 695712508 135336502 8628187 271682264 359567206 392826755 600365552 573625981 134023953 36575477 244547427 2...
output:
NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES YES YES NO NO YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES YES YES NO NO YES YES YES YES YES YES NO NO NO NO YES NO NO NO NO NO YES YES YES NO YES NO NO NO NO YES YES NO YES YES NO YES YES NO YES NO YES NO YES NO NO NO NO NO NO NO...
result:
ok 24979 token(s): yes count is 8477, no count is 16502
Test #11:
score: 0
Accepted
time: 98ms
memory: 8064kb
input:
40000 100000 50000 147020661 440547890 467108725 372744603 670370626 321478575 130607123 29687132 41464204 28780232 155060275 252397560 193516544 219961785 138741566 5634431 606718988 250887247 234303869 182930626 582079699 42853599 154120206 181977264 13052710 428285073 365950339 227725704 31252754...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES ...
result:
ok 24857 token(s): yes count is 24857, no count is 0
Test #12:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
2 1 1 0 999999999 1 1000000000 1 2 1 1
output:
YES
result:
ok YES