Submission #95798

#	Time	Username	Problem	Language	Result	Execution time	Memory
95798		Bodo171	Land of the Rainbow Gold (APIO17_rainbow)	C++14	24 / 100	3013 ms	359236 KiB

rainbow

#include "rainbow.h"
#include <fstream>
#include <iostream>
#include <map>
#include <vector>
#define mp make_pair
using namespace std;
const int nmax=200005;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
map< pair<int,int>,int > rb,norm;
vector<int> ad[10*nmax];
pair<int,int> v[nmax];
int viz[10*nmax];
int a[nmax][2],sum[2][nmax];
int arb[4*nmax];
int n,nr,mnl=2*nmax,mnc=2*nmax,mxl,mxc;
void add_rainbow(int l,int c)
{
    if(!rb[mp(l,c)]) v[++n]={l,c};
    rb[mp(l,c)]=1;
    mnl=min(mnl,l);
    mxl=max(mxl,l);
    mnc=min(mnc,c);
    mxc=max(mxc,c);
}
void add(int l,int c)
{
    int p;
    if((!rb[mp(l,c)])&&(!norm[mp(l,c)]))
        {
            norm[mp(l,c)]=++nr;
            for(int dir=0;dir<4;dir++)
            {
                p=norm[mp(l+d1[dir],c+d2[dir])];
                if(p)
                    ad[p].push_back(nr),ad[nr].push_back(p);
            }
        }
}
int lim,rr,cc,st,dr,ans;
void build(int nod,int l,int r)
{
    if(l==r)
    {
        if(a[l][0]+a[l][1]) arb[nod]=1;
        else arb[nod]=0;
        return;
    }
    int m=(l+r)/2;
    build(2*nod,l,m);
    build(2*nod+1,m+1,r);
    arb[nod]=arb[2*nod]+arb[2*nod+1];
    if((a[m][0]&a[m+1][0])+(a[m][1]&a[m+1][1]))
        arb[nod]--;
}
void query(int nod,int l,int r)
{
    if(st<=l&&r<=dr)
    {
        ans+=arb[nod];
        if(st!=l&&((a[l-1][0]&a[l][0])+(a[l-1][1]&a[l][1])))
            ans--;
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m);
    if(m<dr) query(2*nod+1,m+1,r);
}
int slv(int wh,int l,int r)
{
    int ret=(sum[wh][r]-sum[wh][l-1]);
    if(a[l][wh]==1&&a[l-1][wh]==1)
        ret++;
    return ret;
}
void init(int R, int C, int sr, int sc, int M, char *S) {
    add_rainbow(sr,sc);
    rr=R;cc=C;
    lim=max(R,C);
    if(rr==2)
    {
        for(int i=1;i<=cc;i++)
            for(int j=0;j<2;j++)
              a[i][j]=1;
            a[sc][sr-1]=0;
    }
    for(int i=0;i<M;i++)
    {
        if(S[i]=='N')
            sr--;
        if(S[i]=='S')
            sr++;
        if(S[i]=='W')
           sc--;
        if(S[i]=='E')
          sc++;
        add_rainbow(sr,sc);
        if(rr==2)
        {
            a[sc][sr-1]=0;
        }

    }
    if(rr==2)
    {

        for(int i=0;i<2;i++)
            for(int j=1;j<=cc;j++)
        {
            sum[i][j]=sum[i][j-1];
            if(a[j][i]==1&&a[j-1][i]==0)
                sum[i][j]++;
        }
        build(1,1,cc);
    }
}
void dfs(int x)
{
    viz[x]=1;
    for(int i=0;i<ad[x].size();i++)
        if(!viz[ad[x][i]])
          dfs(ad[x][i]);
}
int colour(int ar, int ac, int br, int bc) {
    int cc=0;
    nr=0;
    if(rr==2)
    {
        ans=0;st=ac;dr=bc;
        if(ar!=br)query(1,1,cc);
        else
        {
            ans=slv(br-1,ac,bc);
        }
        return ans;
    }
    for(int i=1;i<=n;i++)
        for(int p1=-1;p1<=1;p1++)
          for(int p2=-1;p2<=1;p2++)
            if(v[i].first+p1>=ar&&v[i].first+p1<=br&&v[i].second+p2>=ac&&v[i].second+p2<=bc)
          add(v[i].first+p1,v[i].second+p2);
    if(!(ar<mnl&&mxl<br&&ac<mnc&&mxc<bc))
    {
        for(int i=ar; i<=br; i++)
            add(i,ac),add(i,bc);
        for(int i=ac; i<=bc; i++)
            add(ar,i),add(br,i);
    }
     for(int i=1;i<=nr;i++)
        if(!viz[i])
          dfs(i),cc++;
    if(lim<=50)
    {
        norm.clear();
        for(int i=1; i<=nr; i++)
            ad[i].clear(),viz[i]=0;
    }
    return cc;
}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:83:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(int i=1;i<=cc;i++)
         ^~~
rainbow.cpp:86:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             a[sc][sr-1]=0;
             ^
rainbow.cpp: In function 'void dfs(int)':
rainbow.cpp:121:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ad[x].size();i++)
                 ~^~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 24 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26