oj.uz

Submission #1089990

# Submission time Handle Problem Language Result Execution time Memory
1089990 2024-09-17T13:43:23 Z alexander707070 Land of the Rainbow Gold (APIO17_rainbow) C++14
24 / 100
 1380 ms 258080 KB 
#include<bits/stdc++.h>
#include "rainbow.h"

#define MAXN 300007
using namespace std;

int n,m,sx,sy,a,b,c,d,x,y,comps;
string w;

map< pair<int,int> , int > mp;

int table[5][MAXN];

void dfs2(int x,int y){
    table[x][y]=comps;

    if(x>1 and table[x-1][y]==0)dfs2(x-1,y);
    if(x<n and table[x+1][y]==0)dfs2(x+1,y);
    if(y>1 and table[x][y-1]==0)dfs2(x,y-1);
    if(y<m and table[x][y+1]==0)dfs2(x,y+1);
}

void precalc(){
    x=sx; y=sy; table[x][y]=-1;
    for(int i=0;i<w.size();i++){
        if(w[i]=='N')x--;
        if(w[i]=='E')y++;
        if(w[i]=='S')x++;
        if(w[i]=='W')y--;
        table[x][y]=-1;
    }

    for(int f=1;f<=m;f++){
        for(int i=1;i<=n;i++){
            if(table[i][f]==0){
                comps++; dfs2(i,f);
            }
        }
    }
}

int pref[MAXN],suff[MAXN];

void init(int R, int C, int sr, int sc, int M, char *S) {
    n=R; m=C;
    sx=sr; sy=sc;

    for(int i=0;i<M;i++){
        w.push_back(S[i]);
    }

    if(n==2){
        precalc();

        for(int i=1;i<=m;i++){
            pref[i]=max(max(table[1][i],table[2][i]),pref[i-1]);
        }
        
        suff[m+1]=comps+1;
        for(int i=m;i>=1;i--){
            suff[i]=min(min(table[1][i],table[2][i]),suff[i+1]);
        }
    }
}

bool in(int x,int y){
    return x>=a and x<=c and y>=b and y<=d;
}

void check(int x,int y){
    if(in(x-1,y) and mp[{x-1,y}]==0)mp[{x-1,y}]=1;
    if(in(x+1,y) and mp[{x+1,y}]==0)mp[{x+1,y}]=1;
    if(in(x,y-1) and mp[{x,y-1}]==0)mp[{x,y-1}]=1;
    if(in(x,y+1) and mp[{x,y+1}]==0)mp[{x,y+1}]=1;

    if(in(x-1,y-1) and mp[{x-1,y-1}]==0)mp[{x-1,y-1}]=1;
    if(in(x+1,y+1) and mp[{x+1,y+1}]==0)mp[{x+1,y+1}]=1;
    if(in(x+1,y-1) and mp[{x+1,y-1}]==0)mp[{x+1,y-1}]=1;
    if(in(x-1,y+1) and mp[{x-1,y+1}]==0)mp[{x-1,y+1}]=1;
}

void dfs(int x,int y){
    mp[{x,y}]=2;

    if(mp[{x-1,y}]==1)dfs(x-1,y);
    if(mp[{x+1,y}]==1)dfs(x+1,y);
    if(mp[{x,y-1}]==1)dfs(x,y-1);
    if(mp[{x,y+1}]==1)dfs(x,y+1);
}

void calc(int x,int y){
    if(mp[{x-1,y}]==1){dfs(x-1,y);comps++;}
    if(mp[{x+1,y}]==1){dfs(x+1,y);comps++;}
    if(mp[{x,y-1}]==1){dfs(x,y-1);comps++;}
    if(mp[{x,y+1}]==1){dfs(x,y+1);comps++;}
}

int colour(int ar, int ac, int br, int bc){
    a=ar; b=ac;
    c=br; d=bc;

    if(n==2){
        return pref[bc]-suff[ac]+1;
    }

    comps=0; mp.clear();

    for(int i=a;i<=c;i++){
        mp[{i,b}]=mp[{i,d}]=1;
    }

    for(int i=b;i<=d;i++){
        mp[{a,i}]=mp[{c,i}]=1;
    }

    x=sx; y=sy; mp[{x,y}]=-1;
    for(int i=0;i<w.size();i++){
        if(w[i]=='N')x--;
        if(w[i]=='E')y++;
        if(w[i]=='S')x++;
        if(w[i]=='W')y--;
        mp[{x,y}]=-1;
    }

    x=sx; y=sy; check(x,y);
    for(int i=0;i<w.size();i++){
        if(w[i]=='N')x--;
        if(w[i]=='E')y++;
        if(w[i]=='S')x++;
        if(w[i]=='W')y--;
        check(x,y);
    }

    x=sx; y=sy; calc(x,y);
    for(int i=0;i<w.size();i++){
        if(w[i]=='N')x--;
        if(w[i]=='E')y++;
        if(w[i]=='S')x++;
        if(w[i]=='W')y--;
        calc(x,y);
    }

    if(comps==0 and mp[{a,b}]==1)comps++;

    return comps;
}

/*int main(){

    init(6, 4,3, 3, 9,"NWESSWEWS");

    cout<<colour(2,3, 2, 3)<<"\n";
    cout<<colour(3,2, 4, 4)<<"\n";
    cout<<colour(5,3, 6, 4)<<"\n";
    cout<<colour(1,2, 5, 3)<<"\n";
    cout<<colour(4,6,4,6)<<"\n";

    return 0;
}*/

Compilation message

rainbow.cpp: In function 'void precalc()':
rainbow.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 348 KB Output is correct
2 Correct 613 ms 604 KB Output is correct
3 Correct 104 ms 348 KB Output is correct
4 Correct 185 ms 532 KB Output is correct
5 Correct 906 ms 852 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 384 ms 556 KB Output is correct
12 Correct 690 ms 564 KB Output is correct
13 Correct 713 ms 684 KB Output is correct
14 Correct 1380 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 513 ms 98376 KB Output is correct
3 Correct 484 ms 98644 KB Output is correct
4 Correct 458 ms 79700 KB Output is correct
5 Correct 246 ms 49332 KB Output is correct
6 Correct 154 ms 33592 KB Output is correct
7 Correct 312 ms 46992 KB Output is correct
8 Correct 81 ms 17764 KB Output is correct
9 Correct 67 ms 15440 KB Output is correct
10 Correct 32 ms 3920 KB Output is correct
11 Correct 59 ms 12544 KB Output is correct
12 Correct 120 ms 26192 KB Output is correct
13 Correct 98 ms 26264 KB Output is correct
14 Correct 86 ms 19872 KB Output is correct
15 Correct 86 ms 21436 KB Output is correct
16 Correct 131 ms 26956 KB Output is correct
17 Correct 120 ms 27296 KB Output is correct
18 Correct 173 ms 43996 KB Output is correct
19 Correct 657 ms 152656 KB Output is correct
20 Correct 525 ms 106068 KB Output is correct
21 Correct 167 ms 20560 KB Output is correct
22 Correct 159 ms 18512 KB Output is correct
23 Correct 285 ms 64556 KB Output is correct
24 Correct 427 ms 91828 KB Output is correct
25 Correct 562 ms 92860 KB Output is correct
26 Correct 503 ms 104016 KB Output is correct
27 Correct 1166 ms 258080 KB Output is correct
28 Correct 422 ms 87884 KB Output is correct
29 Correct 318 ms 52816 KB Output is correct
30 Correct 339 ms 55696 KB Output is correct
31 Correct 1072 ms 229032 KB Output is correct
32 Correct 1202 ms 240808 KB Output is correct
33 Correct 1169 ms 240976 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 348 KB Output is correct
2 Correct 613 ms 604 KB Output is correct
3 Correct 104 ms 348 KB Output is correct
4 Correct 185 ms 532 KB Output is correct
5 Correct 906 ms 852 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 384 ms 556 KB Output is correct
12 Correct 690 ms 564 KB Output is correct
13 Correct 713 ms 684 KB Output is correct
14 Correct 1380 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 348 KB Output is correct
2 Correct 613 ms 604 KB Output is correct
3 Correct 104 ms 348 KB Output is correct
4 Correct 185 ms 532 KB Output is correct
5 Correct 906 ms 852 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 384 ms 556 KB Output is correct
12 Correct 690 ms 564 KB Output is correct
13 Correct 713 ms 684 KB Output is correct
14 Correct 1380 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -