QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#691103 | #8029. Traveling Merchant | louhao088 | WA | 0ms | 12024kb | C++23 | 2.1kb | 2024-10-31 09:53:58 | 2024-10-31 09:54:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define lowbit(i) (i&(-i))
const int mod=1e9+7,maxn=2e5+5,M=100005;
#define pb push_back
inline int read(){
char ch=getchar();int x=0;bool f=0;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f==1)x=-x;return x;
}
int n,m,x,y,a[maxn],Rt,T,f[maxn][22],dep[maxn],vis[maxn];
char s[maxn];
int st[maxn],dfn[maxn],low[maxn],tot,idx,top,F;
vector<int>e[maxn],g[maxn];
int col[maxn],id[maxn];
int Lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
void tarjan(int x,int fa){
dfn[x]=low[x]=++idx;st[++top]=x;
f[x][0]=fa;dep[x]=dep[fa]+1;
for(auto i:e[x]){
if(dfn[i]){
low[x]=min(low[x],dfn[i]);
continue;
}tarjan(i,x);
low[x]=min(low[x],low[i]);
if(low[i]>=dfn[x]){
tot++;
while(st[top+1]!=i){col[st[top]]=tot;top--;}
id[tot]=x;
}
}
}
void dfs(int x,int fa){
vis[x]=1;
for(auto i:e[x])if(!vis[i]){
dfs(i,x);
}
for(auto i:g[x]){
int z=Lca(i,x);
if(!dfn[i]||!dfn[x])continue;
if(z==i||z==x)F=1;
else if(col[x]==col[z]||col[i]==col[z])F=1;
//else if(id[col[i]]==z||id[col[x]]==z)F=1;
}
}
void solve(){
n=read(),m=read();
scanf("%s",s);
tot=top=idx=F=0;
for(int i=1;i<=m;i++){
x=read(),y=read();
if(s[x]!=s[y])e[x].pb(y),e[y].pb(x);
else g[x].pb(y),g[y].pb(x);
}
tarjan(0,0);
for(int j=1;j<=20;j++)
for(int i=0;i<n;i++)
f[i][j]=f[f[i][j-1]][j-1];
dfs(0,0);
if(F)puts("yes");
else puts("no");
for(int i=0;i<n;i++)e[i].clear(),g[i].clear(),dfn[i]=vis[i]=low[i]=col[i]=id[i]=dep[i]=0;
for(int i=0;i<n;i++)for(int j=0;j<=20;j++)f[i][j]=0;
}
int main() {
T=read();
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 12024kb
input:
2 4 4 LHLH 0 1 1 2 1 3 2 3 3 3 LHH 0 1 0 2 1 2
output:
yes yes
result:
wrong answer 2nd lines differ - expected: 'no', found: 'yes'