oj.uz

Submission #95794

# Submission time Handle Problem Language Result Execution time Memory
95794 2019-02-02T16:01:58 Z Bodo171 Land of the Rainbow Gold (APIO17_rainbow) C++14
35 / 100
 3000 ms 359032 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 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;
void init(int R, int C, int sr, int sc, int M, char *S) {
    add_rainbow(sr,sc);
    lim=max(R,C);
    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);

    }
}
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;
    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 dfs(int)':
rainbow.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ad[x].size();i++)
                 ~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 47328 KB Output is correct
2 Correct 215 ms 47612 KB Output is correct
3 Correct 130 ms 47480 KB Output is correct
4 Correct 148 ms 47612 KB Output is correct
5 Correct 231 ms 47720 KB Output is correct
6 Correct 43 ms 47352 KB Output is correct
7 Correct 46 ms 47352 KB Output is correct
8 Correct 43 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 209 ms 47568 KB Output is correct
12 Correct 283 ms 47608 KB Output is correct
13 Correct 477 ms 48012 KB Output is correct
14 Correct 470 ms 47736 KB Output is correct
15 Correct 45 ms 47224 KB Output is correct
16 Correct 44 ms 47352 KB Output is correct
17 Correct 47 ms 47224 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 47 ms 47224 KB Output is correct
3 Execution timed out 3042 ms 138168 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47224 KB Output is correct
2 Correct 1266 ms 172116 KB Output is correct
3 Correct 1241 ms 172148 KB Output is correct
4 Correct 1154 ms 162784 KB Output is correct
5 Correct 613 ms 109560 KB Output is correct
6 Correct 1347 ms 205944 KB Output is correct
7 Correct 141 ms 55416 KB Output is correct
8 Correct 129 ms 60160 KB Output is correct
9 Correct 97 ms 55936 KB Output is correct
10 Correct 75 ms 51192 KB Output is correct
11 Correct 169 ms 64676 KB Output is correct
12 Correct 386 ms 89328 KB Output is correct
13 Correct 355 ms 89208 KB Output is correct
14 Correct 359 ms 89336 KB Output is correct
15 Correct 341 ms 87544 KB Output is correct
16 Correct 1086 ms 174912 KB Output is correct
17 Correct 959 ms 165496 KB Output is correct
18 Correct 1253 ms 210552 KB Output is correct
19 Correct 1401 ms 221304 KB Output is correct
20 Correct 1146 ms 178040 KB Output is correct
21 Correct 277 ms 77176 KB Output is correct
22 Correct 275 ms 75384 KB Output is correct
23 Correct 494 ms 117244 KB Output is correct
24 Correct 773 ms 150904 KB Output is correct
25 Correct 852 ms 111736 KB Output is correct
26 Correct 722 ms 111736 KB Output is correct
27 Correct 2518 ms 359032 KB Output is correct
28 Correct 558 ms 95828 KB Output is correct
29 Correct 76 ms 50680 KB Output is correct
30 Correct 119 ms 55516 KB Output is correct
31 Correct 2407 ms 330464 KB Output is correct
32 Correct 2529 ms 336760 KB Output is correct
33 Correct 2727 ms 336968 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 47328 KB Output is correct
2 Correct 215 ms 47612 KB Output is correct
3 Correct 130 ms 47480 KB Output is correct
4 Correct 148 ms 47612 KB Output is correct
5 Correct 231 ms 47720 KB Output is correct
6 Correct 43 ms 47352 KB Output is correct
7 Correct 46 ms 47352 KB Output is correct
8 Correct 43 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 209 ms 47568 KB Output is correct
12 Correct 283 ms 47608 KB Output is correct
13 Correct 477 ms 48012 KB Output is correct
14 Correct 470 ms 47736 KB Output is correct
15 Correct 45 ms 47224 KB Output is correct
16 Correct 44 ms 47352 KB Output is correct
17 Correct 47 ms 47224 KB Output is correct
18 Execution timed out 3057 ms 117628 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 47328 KB Output is correct
2 Correct 215 ms 47612 KB Output is correct
3 Correct 130 ms 47480 KB Output is correct
4 Correct 148 ms 47612 KB Output is correct
5 Correct 231 ms 47720 KB Output is correct
6 Correct 43 ms 47352 KB Output is correct
7 Correct 46 ms 47352 KB Output is correct
8 Correct 43 ms 47352 KB Output is correct
9 Correct 44 ms 47352 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 209 ms 47568 KB Output is correct
12 Correct 283 ms 47608 KB Output is correct
13 Correct 477 ms 48012 KB Output is correct
14 Correct 470 ms 47736 KB Output is correct
15 Correct 45 ms 47224 KB Output is correct
16 Correct 44 ms 47352 KB Output is correct
17 Correct 47 ms 47224 KB Output is correct
18 Execution timed out 3057 ms 117628 KB Time limit exceeded
19 Halted 0 ms 0 KB -