QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#690026 | #3572. Idol | bluejellyfish | 100 ✓ | 9ms | 3932kb | C++23 | 2.5kb | 2024-10-30 19:52:05 | 2024-10-30 19:52:06 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stack>
#include<queue>
#define MAXN 2205
#define MAXM 25005
#define oo 1000000007
#define ll long long
using namespace std;
struct node
{
int u,v,next;
}edge[MAXM];
int ne,_next[MAXN],DfsIndex,tpnum,tp[MAXN],dfn[MAXN],low[MAXN];
void addedge(int u,int v)
{
edge[++ne].next=_next[u],_next[u]=ne;
edge[ne].u=u,edge[ne].v=v;
}
bool instack[MAXN];
stack<int> S;
void tarjan(int x)
{
dfn[x]=low[x]=++DfsIndex;
instack[x]=true,S.push(x);
for (int k=_next[x];k;k=edge[k].next)
{
int v=edge[k].v;
if (!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}else
if (instack[v])
low[x]=min(low[x],dfn[v]);
}
if (dfn[x]==low[x])
{
tpnum++;
do
{
x=S.top(),S.pop();
instack[x]=false;
tp[x]=tpnum;
}while (low[x]!=dfn[x]);
}
}
bool color[MAXN];
bool judge(int n)
{
for (int i=1;i<=n;i++)
{
if (tp[i<<1]==tp[i<<1|1]) return false;
if (color[i<<1] && color[i<<1|1]) return false;
}
return true;
}
void dfs(int x)
{
color[x]=1;
for (int k=_next[x];k;k=edge[k].next)
if (!color[edge[k].v]) dfs(edge[k].v);
}
int main()
{
int n,m,u,v,i;
while (~scanf("%d%d",&n,&m))
{
ne=0,memset(_next,0,sizeof(_next));
while (m--)
{
scanf("%d%d",&u,&v);
if (u<0) u=(-u)<<1;
else u=u<<1|1;
if (v<0) v=(-v)<<1;
else v=v<<1|1;
addedge(u^1,v),addedge(v^1,u);
}
memset(dfn,0,sizeof(dfn));
memset(instack,false,sizeof(instack));
while (!S.empty()) S.pop();
tpnum=DfsIndex=0;
for (i=2;i<=(n<<1|1);i++)
if (!dfn[i]) tarjan(i);
memset(color,false,sizeof(color));
dfs(3);
if (!judge(n)) printf("no\n");
else printf("yes\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 100
Accepted
time: 9ms
memory: 3932kb
input:
4 3 1 2 -2 -3 2 4 2 4 1 2 1 -2 -1 2 -1 -2 2 4 -1 2 1 2 -1 -2 1 -2 3 16 -1 2 -2 3 1 2 -2 3 -1 -2 2 3 1 -2 2 3 -1 2 -2 -3 1 2 -2 -3 -1 -2 2 -3 1 -2 2 -3 4 48 -1 2 -2 3 -3 4 1 2 -2 3 -3 4 -1 -2 2 3 -3 4 1 -2 2 3 -3 4 -1 2 -2 -3 3 4 1 2 -2 -3 3 4 -1 -2 2 -3 3 4 1 -2 2 -3 3 4 -1 2 -2 3 -3 -4 1 2 -2 3 -3 ...
output:
yes no no no no no no no no yes yes yes yes yes yes yes yes yes yes yes yes yes no yes yes no yes no yes yes yes no no yes yes yes yes no 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 ye...
result:
ok 117 lines