QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#385614 | #5101. Crystal Crosswind | SolitaryDream# | RE | 8ms | 85672kb | C++17 | 2.8kb | 2024-04-10 21:41:40 | 2024-04-10 21:41:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e3+7;
int n,m;
int k;
int c[N];
vector<int> e[N],g[N],h[N];
int id(int x,int y)
{
return (x-1)*m+y;
}
int dfn[N],low[N],bel[N],scc,dc,in[N];
vector<int> st;
int col[N],sz[N];
void tarjan(int x)
{
dfn[x]=low[x]=++dc;
st.push_back(x);
in[x]=1;
for(auto v:e[x])
{
if(!dfn[v])
tarjan(v),low[x]=min(low[x],low[v]);
else if(in[v])
low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x])
{
int y;
++scc;
do {
y=st.back();
st.pop_back();
bel[y]=scc;
sz[scc]++;
in[y]=0;
}while(y!=x);
}
}
int vis[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n*m;i++)
c[i]=-1;
for(int r=1;r<=k;r++)
{
int wx,wy;
cin>>wx>>wy;
int u;
cin>>u;
while(u--)
{
int a,b;
cin>>a>>b;
vis[id(a,b)]=r;
c[id(a,b)]=1;
if(a-wx>=1&&a-wx<=n&&b-wy>=1&&b-wy<=m)
c[id(a-wx,b-wy)]=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(vis[id(i,j)]==r)
continue;
if(i-wx>=1&&i-wx<=n&&j-wy>=1&&j-wy<=m)
{
e[id(i,j)].push_back(id(i-wx,j-wy));
}
else
c[id(i,j)]=0;
}
}
int V=n*m;
for(int i=1;i<=V;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=V;i++)
for(auto j:e[i])
if(bel[i]!=bel[j])
g[bel[i]].push_back(bel[j]),h[bel[j]].push_back(bel[i]);
for(int i=1;i<=scc;i++)
col[i]=-1;
for(int i=1;i<=V;i++)
{
assert(col[bel[i]]==-1||col[bel[i]]==c[i]);
col[bel[i]]=c[i];
}
for(int i=scc;i>=1;i--)
{
if(col[i]!=1)
continue;
for(auto v:g[i])
col[v]=1;
}
for(int i=1;i<=scc;i++)
{
if(col[i]!=0)
continue;
for(auto v:h[i])
col[v]=0;
}
for(int j=1;j<=m;j++,cout<<"\n")
for(int i=1;i<=n;i++)
{
int x=id(i,j);
if(col[bel[x]]!=-1)
cout<<".#"[col[bel[x]]];
else
cout<<".";
}
cout<<"\n";
for(int j=1;j<=m;j++,cout<<"\n")
for(int i=1;i<=n;i++)
{
int x=id(i,j);
if(col[bel[x]]!=-1)
cout<<".#"[col[bel[x]]];
else
cout<<"#";
}
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 85672kb
input:
4 1 1 0 1 2 1 1 3 1
output:
#.#. #.#.
result:
ok 3 lines
Test #2:
score: -100
Runtime Error
input:
4 4 2 1 0 4 2 4 2 1 1 3 1 2 -1 0 4 4 3 4 2 3 1 3 4