QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#385614#5101. Crystal CrosswindSolitaryDream#RE 8ms85672kbC++172.8kb2024-04-10 21:41:402024-04-10 21:41:41

Judging History

你现在查看的是最新测评结果

  • [2024-04-10 21:41:41]
  • 评测
  • 测评结果:RE
  • 用时:8ms
  • 内存:85672kb
  • [2024-04-10 21:41:40]
  • 提交

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<<"#";
        }
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: