Submission #75600

#	Time	Username	Problem	Language	Result	Execution time	Memory
75600		vex	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	71 ms	71532 KiB

dango_maker

#include <bits/stdc++.h>
#define maxn 3005
#define maxnode maxn*maxn/3
#define INF 1000000000
using namespace std;

int n,m;
char a[maxn][maxn];

int r[maxn][maxn];
int d[maxn][maxn];

int uk=0;
vector<int>adj[maxnode];

int dp[maxnode][2];
bool bio[maxnode];

int cyc=0;
int t[maxnode];
int lu[maxnode/4];
int ld[maxnode/4];
int ru[maxnode/4];
int rd[maxnode/4];
int dpcyc[maxnode/4][9];
//kolicnik gore
//ostatak dole
bool bcyc[maxnode/4];

bool proso(int v)
{
    if(bio[v])return true;
    if(t[v]!=-1 && bcyc[t[v]])return true;
    return false;
}
void dfs(int v)
{
    dp[v][0]=0;
    dp[v][1]=1;
    bio[v]=true;

    if(t[v]!=-1)
    {
        int tt=t[v];
        bcyc[tt]=true;

        for(auto x:adj[ld[tt]])
        {
            if(proso(x))continue;

            dfs(x);
            for(int k=0;k<9;k++)
            {
                if(k%3!=1)dpcyc[tt][k]+=max(dp[x][0],dp[x][1]);
                else dpcyc[tt][k]+=dp[x][0];
            }
        }
        for(auto x:adj[lu[tt]])
        {
            if(proso(x))continue;

            dfs(x);
            for(int k=0;k<9;k++)
            {
                if(k/3!=1)dpcyc[tt][k]+=max(dp[x][0],dp[x][1]);
                else dpcyc[tt][k]+=dp[x][0];
            }
        }
        for(auto x:adj[rd[tt]])
        {
            if(proso(x))continue;

            dfs(x);
            for(int k=0;k<9;k++)
            {
                if(k%3!=2)dpcyc[tt][k]+=max(dp[x][0],dp[x][1]);
                else dpcyc[tt][k]+=dp[x][0];
            }
        }
        for(auto x:adj[ru[tt]])
        {
            if(proso(x))continue;

            dfs(x);
            for(int k=0;k<9;k++)
            {
                if(k/3!=2)dpcyc[tt][k]+=max(dp[x][0],dp[x][1]);
                else dpcyc[tt][k]+=dp[x][0];
            }
        }
    }
    else{
        for(auto x:adj[v])
        {
            if(proso(x))continue;

            dfs(x);
            if(t[x]!=-1)
            {
                int tt=t[x];

                if(x==lu[tt])
                {
                    int dod0=0;
                    int dod1=0;
                    for(int k=0;k<9;k++)
                    {
                        dod0=max(dod0,dpcyc[tt][k]);
                        if(k/3!=1)dod1=max(dod1,dpcyc[tt][k]);
                    }
                    dp[v][0]+=dod0;
                    dp[v][1]+=dod1;
                }

                if(x==ld[tt])
                {
                    int dod0=0;
                    int dod1=0;
                    for(int k=0;k<9;k++)
                    {
                        dod0=max(dod0,dpcyc[tt][k]);
                        if(k%3!=1)dod1=max(dod1,dpcyc[tt][k]);
                    }
                    dp[v][0]+=dod0;
                    dp[v][1]+=dod1;
                }

                if(x==rd[tt])
                {
                    int dod0=0;
                    int dod1=0;
                    for(int k=0;k<9;k++)
                    {
                        dod0=max(dod0,dpcyc[tt][k]);
                        if(k%3!=2)dod1=max(dod1,dpcyc[tt][k]);
                    }
                    dp[v][0]+=dod0;
                    dp[v][1]+=dod1;
                }

                if(x==ru[tt])
                {
                    int dod0=0;
                    int dod1=0;
                    for(int k=0;k<9;k++)
                    {
                        dod0=max(dod0,dpcyc[tt][k]);
                        if(k/3!=2)dod1=max(dod1,dpcyc[tt][k]);
                    }
                    dp[v][0]+=dod0;
                    dp[v][1]+=dod1;
                }
            }

            else
            {
                dp[v][0]+=max(dp[x][0],dp[x][1]);
                dp[v][1]+=dp[x][0];
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];

    for(int i=0;i<n;i++)for(int j=0;j<m;j++)
    {
        if(j+2<m && a[i][j]=='R' && a[i][j+1]=='G' && a[i][j+2]=='W')
        {
            r[i][j]=uk;
            uk++;
        }
        else r[i][j]=-1;

        if(i+2<n && a[i][j]=='R' && a[i+1][j]=='G' && a[i+2][j]=='W')
        {
            d[i][j]=uk;
            uk++;
        }
        else d[i][j]=-1;
    }

    for(int i=0;i<uk;i++)t[i]=-1;

    for(int i=0;i<n;i++)for(int j=0;j<m;j++)
    {
        if(d[i][j]!=-1)
        {
            if(r[i][j]!=-1)adj[d[i][j]].push_back(r[i][j]);
            if(j-1>=0 && r[i+1][j-1]!=-1)adj[d[i][j]].push_back(r[i+1][j-1]);
            if(j-2>=0 && r[i+2][j-2]!=-2)adj[d[i][j]].push_back(r[i+2][j-2]);

            if(i+2<n && j-2>=0 && r[i+1][j-1]!=-1 && r[i+2][j-2]!=-1 && d[i+1][j-1]!=-1)
            {
                int xx=d[i][j];
                int yy=r[i+1][j-1];
                int zz=r[i+2][j-2];
                int tt=d[i+1][j-1];

                int br=t[xx];
                if(t[yy]!=-1)br=t[yy];
                if(t[zz]!=-1)br=t[zz];
                if(t[tt]!=-1)br=t[tt];

                if(br==-1)
                {
                    br=cyc;
                    cyc++;

                    lu[br]=xx;
                    ru[br]=yy;

                    for(int k=0;k<9;k++)
                    {
                        if(k%3==0 && k/3==0)dpcyc[br][k]=0;
                        else if(k%3==0 || k/3==0)dpcyc[br][k]=1;
                        else if(k/3==k%3)dpcyc[br][k]=-INF;
                        else dpcyc[br][k]=2;
                    }
                }
                else
                {
                    int asd[9];
                    for(int k=0;k<9;k++)
                    {
                        if(k%3==0 || k/3==0)asd[k]=dpcyc[br][k]+1;
                        else
                        {
                            int maxx=0;
                            for(int kk=0;kk<9;kk++)if(kk%3!=k%3 && maxx<dpcyc[br][kk])maxx=dpcyc[br][kk];
                            asd[k]=maxx+1;
                        }
                    }
                    for(int k=0;k<9;k++)dpcyc[br][k]=asd[k];
                }

                t[xx]=t[yy]=t[zz]=t[tt]=br;

                rd[br]=tt;
                ld[br]=zz;
            }
        }

        if(r[i][j]!=-1)
        {
            if(d[i][j]!=-1)adj[r[i][j]].push_back(d[i][j]);
            if(i-1>=0 && d[i-1][j+1]!=-1)adj[r[i][j]].push_back(d[i-1][j+1]);
            if(i-2>=0 && d[i-2][j+2]!=-1)adj[r[i][j]].push_back(d[i-2][j+2]);

            if(i+1<n && i-1>=0 && j+1<m && j-1>=0 && d[i-1][j+1]!=-1 && r[i+1][j-1]!=-1 && d[i][j]!=-1)
            {
                int xx=d[i-1][j+1];
                int yy=r[i][j];
                int zz=r[i+1][j-1];
                int tt=d[i][j];

                int br=t[xx];
                if(t[yy]!=-1)br=t[yy];
                if(t[zz]!=-1)br=t[zz];
                if(t[tt]!=-1)br=t[tt];

                if(br==-1)
                {
                    br=cyc;
                    cyc++;

                    lu[br]=xx;
                    ru[br]=yy;

                    for(int k=0;k<9;k++)
                    {
                        if(k%3==0 && k/3==0)dpcyc[br][k]=0;
                        else if(k%3==0 || k/3==0)dpcyc[br][k]=1;
                        else if(k/3==k%3)dpcyc[br][k]=-INF;
                        else dpcyc[br][k]=2;
                    }
                }
                else
                {
                    int asd[9];
                    for(int k=0;k<9;k++)
                    {
                        if(k%3==0 || k/3==0)asd[k]=dpcyc[br][k]+1;
                        else
                        {
                            int maxx=0;
                            for(int kk=0;kk<9;kk++)if(kk%3!=k%3 && maxx<dpcyc[br][kk])maxx=dpcyc[br][kk];
                            asd[k]=maxx+1;
                        }
                    }
                    for(int k=0;k<9;k++)dpcyc[br][k]=asd[k];
                }

                t[xx]=t[yy]=t[zz]=t[tt]=br;

                rd[br]=tt;
                ld[br]=zz;
            }
        }
    }

    int sol=0;
    for(int i=0;i<uk;i++)bio[i]=false;
    for(int i=0;i<cyc;i++)bcyc[i]=false;
    for(int i=0;i<uk;i++)if(!proso(i))
    {
        dfs(i);
        if(t[i]==-1)sol+=max(dp[i][0],dp[i][1]);
        else{
            int maxx=0;
            for(int k=0;k<9;k++)if(maxx<dpcyc[t[i]][k])maxx=dpcyc[t[i]][k];
            sol+=maxx;
        }
    }

    cout<<sol<<endl;
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67