oj.uz

Submission #95797

# Submission time Handle Problem Language Result Execution time Memory
95797 2019-02-02T17:00:02 Z Bodo171 Land of the Rainbow Gold (APIO17_rainbow) C++14
24 / 100
 3000 ms 359196 KB 
#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[2][nmax],sum[nmax][2];
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 47480 KB Output is correct
2 Correct 211 ms 47736 KB Output is correct
3 Correct 128 ms 47576 KB Output is correct
4 Correct 152 ms 47572 KB Output is correct
5 Correct 235 ms 47796 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 45 ms 47272 KB Output is correct
8 Correct 41 ms 47480 KB Output is correct
9 Correct 45 ms 47352 KB Output is correct
10 Correct 44 ms 47256 KB Output is correct
11 Correct 211 ms 47636 KB Output is correct
12 Correct 439 ms 47736 KB Output is correct
13 Correct 468 ms 47736 KB Output is correct
14 Correct 469 ms 47736 KB Output is correct
15 Correct 37 ms 47224 KB Output is correct
16 Execution timed out 3023 ms 47352 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3023 ms 47352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 47224 KB Output is correct
2 Correct 1255 ms 171876 KB Output is correct
3 Correct 1154 ms 172084 KB Output is correct
4 Correct 1030 ms 162548 KB Output is correct
5 Correct 616 ms 109304 KB Output is correct
6 Correct 1227 ms 205760 KB Output is correct
7 Correct 140 ms 55288 KB Output is correct
8 Correct 126 ms 60044 KB Output is correct
9 Correct 97 ms 55800 KB Output is correct
10 Correct 74 ms 51084 KB Output is correct
11 Correct 148 ms 64504 KB Output is correct
12 Correct 318 ms 89232 KB Output is correct
13 Correct 329 ms 89224 KB Output is correct
14 Correct 358 ms 89088 KB Output is correct
15 Correct 340 ms 87416 KB Output is correct
16 Correct 1105 ms 174856 KB Output is correct
17 Correct 1004 ms 165412 KB Output is correct
18 Correct 1373 ms 210432 KB Output is correct
19 Correct 1558 ms 221060 KB Output is correct
20 Correct 1242 ms 178032 KB Output is correct
21 Correct 327 ms 76928 KB Output is correct
22 Correct 280 ms 75348 KB Output is correct
23 Correct 499 ms 117356 KB Output is correct
24 Correct 760 ms 150732 KB Output is correct
25 Correct 836 ms 111612 KB Output is correct
26 Correct 732 ms 111664 KB Output is correct
27 Correct 2626 ms 359196 KB Output is correct
28 Correct 575 ms 95736 KB Output is correct
29 Correct 77 ms 50680 KB Output is correct
30 Correct 140 ms 55556 KB Output is correct
31 Correct 2646 ms 330348 KB Output is correct
32 Correct 2462 ms 336900 KB Output is correct
33 Correct 2534 ms 336940 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 47480 KB Output is correct
2 Correct 211 ms 47736 KB Output is correct
3 Correct 128 ms 47576 KB Output is correct
4 Correct 152 ms 47572 KB Output is correct
5 Correct 235 ms 47796 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 45 ms 47272 KB Output is correct
8 Correct 41 ms 47480 KB Output is correct
9 Correct 45 ms 47352 KB Output is correct
10 Correct 44 ms 47256 KB Output is correct
11 Correct 211 ms 47636 KB Output is correct
12 Correct 439 ms 47736 KB Output is correct
13 Correct 468 ms 47736 KB Output is correct
14 Correct 469 ms 47736 KB Output is correct
15 Correct 37 ms 47224 KB Output is correct
16 Execution timed out 3023 ms 47352 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 47480 KB Output is correct
2 Correct 211 ms 47736 KB Output is correct
3 Correct 128 ms 47576 KB Output is correct
4 Correct 152 ms 47572 KB Output is correct
5 Correct 235 ms 47796 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 45 ms 47272 KB Output is correct
8 Correct 41 ms 47480 KB Output is correct
9 Correct 45 ms 47352 KB Output is correct
10 Correct 44 ms 47256 KB Output is correct
11 Correct 211 ms 47636 KB Output is correct
12 Correct 439 ms 47736 KB Output is correct
13 Correct 468 ms 47736 KB Output is correct
14 Correct 469 ms 47736 KB Output is correct
15 Correct 37 ms 47224 KB Output is correct
16 Execution timed out 3023 ms 47352 KB Time limit exceeded
17 Halted 0 ms 0 KB -