QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #53807 | #1869. Power Station of Art | 2022zll | AC ✓ | 158ms | 17076kb | C++ | 1.9kb | 2022-10-05 22:58:13 | 2022-10-05 22:58:14 |
Judging History
answer
#include<algorithm>
#include<cstdio>
#include<cstring>
void read(int&num){
int ch=getchar();
num=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
const int maxn=1000005,maxm=1000005;
char s[maxn];
int T,n,m,head[maxn],total;
struct Edge{
int to,next;
}e[maxm<<1];
void add(int u,int v){
e[++total]=Edge{v,head[u]};
head[u]=total;
}
int col[maxn],inv[2][maxn],inc[2][maxn];
int flag,vis_cnt;
struct Data{
int first,second;
}st[2][maxn];
bool operator<(const Data a,const Data b){
return a.first!=b.first?a.first<b.first:a.second<b.second;
}
bool operator!=(const Data a,const Data b){
return a.first!=b.first||a.second!=b.second;
}
void dfs(int u){
vis_cnt++;
for(int op=0;op<=1;op++)st[op][vis_cnt]=Data{inv[op][u],inc[op][u]^col[u]};
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(col[v]==-1){
col[v]=col[u]^1;
dfs(v);
}else if(col[u]==col[v])flag=1;
}
}
bool work(int task){
read(n),read(m);
memset(col+1,-1,sizeof(int)*n);
if(task>1){
memset(head+1,0,sizeof(int)*n);
total=0;
}
for(int i=1,u,v;i<=m;i++){
read(u),read(v);
add(u,v),add(v,u);
}
for(int op=0;op<=1;op++){
for(int i=1;i<=n;i++)read(inv[op][i]);
scanf("%s",s+1);
for(int i=1;i<=n;i++)inc[op][i]=(s[i]=='R');
}
for(int i=1;i<=n;i++)
if(col[i]==-1){
flag=vis_cnt=0;
col[i]=0;
dfs(i);
for(int op=0;op<=1;op++)std::sort(st[op]+1,st[op]+vis_cnt+1);
if(flag){
int tmp=0;
for(int op=0;op<=1;op++)
for(int i=1;i<=vis_cnt;i++)
tmp^=st[op][i].second;
if(tmp)return false;
for(int i=1;i<=vis_cnt;i++)
if(st[0][i].first!=st[1][i].first)
return false;
}else{
for(int i=1;i<=vis_cnt;i++)
if(st[0][i]!=st[1][i])
return false;
}
}
return true;
}
int main(){
read(T);
for(int i=1;i<=T;i++)puts(work(i)?"YES":"NO");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 2024kb
input:
3 2 1 1 2 3 4 RR 4 3 BB 3 2 1 2 2 3 1 1 1 RBR 1 1 1 BBB 3 3 1 2 2 3 3 1 1 1 1 RBR 1 1 1 BBB
output:
YES NO YES
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 158ms
memory: 17076kb
input:
25054 5 10 4 5 4 2 4 3 4 1 5 2 5 3 5 1 2 3 2 1 3 1 12 2 9 10 7 RRRBB 10 2 9 7 12 RRBRB 1 0 4 R 4 R 8 4 4 3 1 5 8 5 6 5 7 2 11 10 9 6 3 5 RBRBBRBR 7 2 10 11 6 5 3 9 RBRBBRBR 7 4 7 2 5 1 5 6 5 4 12 5 9 14 5 12 12 RRBRBRR 14 12 9 5 12 12 5 RBBRBRB 10 1 4 6 5 3 2 9 7 3 11 11 6 8 RRRBRRBBBR 5 3 2 3 7 9 1...
output:
YES YES YES YES YES YES YES YES YES NO YES NO YES NO NO YES YES YES NO YES NO YES YES NO YES YES NO YES NO YES YES YES YES NO YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO NO YES NO YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO YES NO NO...
result:
ok 25054 lines