oj.uz

Submission #95798

# Submission time Handle Problem Language Result Execution time Memory
95798 2019-02-02T17:06:12 Z Bodo171 Land of the Rainbow Gold (APIO17_rainbow) C++14
24 / 100
 3000 ms 359236 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[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

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 79 ms 47352 KB Output is correct
2 Correct 209 ms 47700 KB Output is correct
3 Correct 126 ms 47688 KB Output is correct
4 Correct 147 ms 47728 KB Output is correct
5 Correct 230 ms 47676 KB Output is correct
6 Correct 45 ms 47352 KB Output is correct
7 Correct 45 ms 47452 KB Output is correct
8 Correct 44 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 43 ms 47356 KB Output is correct
11 Correct 206 ms 47656 KB Output is correct
12 Correct 275 ms 47660 KB Output is correct
13 Correct 499 ms 47864 KB Output is correct
14 Correct 482 ms 47736 KB Output is correct
15 Correct 44 ms 47352 KB Output is correct
16 Execution timed out 3013 ms 47316 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 3013 ms 47316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 1278 ms 172068 KB Output is correct
3 Correct 1135 ms 172252 KB Output is correct
4 Correct 1098 ms 162644 KB Output is correct
5 Correct 614 ms 109368 KB Output is correct
6 Correct 1406 ms 205736 KB Output is correct
7 Correct 141 ms 55448 KB Output is correct
8 Correct 122 ms 60124 KB Output is correct
9 Correct 93 ms 55928 KB Output is correct
10 Correct 77 ms 51192 KB Output is correct
11 Correct 158 ms 64588 KB Output is correct
12 Correct 363 ms 89312 KB Output is correct
13 Correct 372 ms 89336 KB Output is correct
14 Correct 344 ms 89336 KB Output is correct
15 Correct 343 ms 87416 KB Output is correct
16 Correct 1079 ms 174780 KB Output is correct
17 Correct 1018 ms 165340 KB Output is correct
18 Correct 1426 ms 210608 KB Output is correct
19 Correct 1462 ms 221220 KB Output is correct
20 Correct 1129 ms 178040 KB Output is correct
21 Correct 280 ms 76920 KB Output is correct
22 Correct 279 ms 75448 KB Output is correct
23 Correct 549 ms 117368 KB Output is correct
24 Correct 858 ms 150804 KB Output is correct
25 Correct 928 ms 111736 KB Output is correct
26 Correct 793 ms 111604 KB Output is correct
27 Correct 2693 ms 359236 KB Output is correct
28 Correct 550 ms 95604 KB Output is correct
29 Correct 75 ms 50552 KB Output is correct
30 Correct 120 ms 55440 KB Output is correct
31 Correct 2329 ms 330272 KB Output is correct
32 Correct 2483 ms 336752 KB Output is correct
33 Correct 2555 ms 336684 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 47352 KB Output is correct
2 Correct 209 ms 47700 KB Output is correct
3 Correct 126 ms 47688 KB Output is correct
4 Correct 147 ms 47728 KB Output is correct
5 Correct 230 ms 47676 KB Output is correct
6 Correct 45 ms 47352 KB Output is correct
7 Correct 45 ms 47452 KB Output is correct
8 Correct 44 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 43 ms 47356 KB Output is correct
11 Correct 206 ms 47656 KB Output is correct
12 Correct 275 ms 47660 KB Output is correct
13 Correct 499 ms 47864 KB Output is correct
14 Correct 482 ms 47736 KB Output is correct
15 Correct 44 ms 47352 KB Output is correct
16 Execution timed out 3013 ms 47316 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 47352 KB Output is correct
2 Correct 209 ms 47700 KB Output is correct
3 Correct 126 ms 47688 KB Output is correct
4 Correct 147 ms 47728 KB Output is correct
5 Correct 230 ms 47676 KB Output is correct
6 Correct 45 ms 47352 KB Output is correct
7 Correct 45 ms 47452 KB Output is correct
8 Correct 44 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 43 ms 47356 KB Output is correct
11 Correct 206 ms 47656 KB Output is correct
12 Correct 275 ms 47660 KB Output is correct
13 Correct 499 ms 47864 KB Output is correct
14 Correct 482 ms 47736 KB Output is correct
15 Correct 44 ms 47352 KB Output is correct
16 Execution timed out 3013 ms 47316 KB Time limit exceeded
17 Halted 0 ms 0 KB -