oj.uz

Submission #1089988

# Submission time Handle Problem Language Result Execution time Memory
1089988 2024-09-17T13:42:46 Z alexander707070 Land of the Rainbow Gold (APIO17_rainbow) C++14
24 / 100
 1383 ms 258036 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]);
        }
        for(int i=m;i>=1;i--){
            suff[i]=max(max(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:115:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp:133:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 348 KB Output is correct
2 Correct 609 ms 608 KB Output is correct
3 Correct 106 ms 528 KB Output is correct
4 Correct 179 ms 344 KB Output is correct
5 Correct 893 ms 460 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 392 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 388 ms 560 KB Output is correct
12 Correct 700 ms 344 KB Output is correct
13 Correct 728 ms 848 KB Output is correct
14 Correct 1383 ms 600 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 536 ms 98428 KB Output is correct
3 Correct 495 ms 98376 KB Output is correct
4 Correct 462 ms 79664 KB Output is correct
5 Correct 251 ms 49488 KB Output is correct
6 Correct 161 ms 33648 KB Output is correct
7 Correct 320 ms 47216 KB Output is correct
8 Correct 80 ms 17748 KB Output is correct
9 Correct 74 ms 15436 KB Output is correct
10 Correct 31 ms 3924 KB Output is correct
11 Correct 56 ms 12516 KB Output is correct
12 Correct 127 ms 26448 KB Output is correct
13 Correct 95 ms 26156 KB Output is correct
14 Correct 86 ms 19936 KB Output is correct
15 Correct 84 ms 21584 KB Output is correct
16 Correct 130 ms 26964 KB Output is correct
17 Correct 115 ms 27152 KB Output is correct
18 Correct 167 ms 44000 KB Output is correct
19 Correct 683 ms 152604 KB Output is correct
20 Correct 540 ms 105960 KB Output is correct
21 Correct 173 ms 20564 KB Output is correct
22 Correct 175 ms 18516 KB Output is correct
23 Correct 264 ms 64596 KB Output is correct
24 Correct 403 ms 91984 KB Output is correct
25 Correct 522 ms 93012 KB Output is correct
26 Correct 471 ms 104020 KB Output is correct
27 Correct 1188 ms 258036 KB Output is correct
28 Correct 426 ms 87888 KB Output is correct
29 Correct 307 ms 53076 KB Output is correct
30 Correct 343 ms 55612 KB Output is correct
31 Correct 1060 ms 229472 KB Output is correct
32 Correct 1157 ms 240980 KB Output is correct
33 Correct 1243 ms 240976 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 348 KB Output is correct
2 Correct 609 ms 608 KB Output is correct
3 Correct 106 ms 528 KB Output is correct
4 Correct 179 ms 344 KB Output is correct
5 Correct 893 ms 460 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 392 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 388 ms 560 KB Output is correct
12 Correct 700 ms 344 KB Output is correct
13 Correct 728 ms 848 KB Output is correct
14 Correct 1383 ms 600 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 104 ms 348 KB Output is correct
2 Correct 609 ms 608 KB Output is correct
3 Correct 106 ms 528 KB Output is correct
4 Correct 179 ms 344 KB Output is correct
5 Correct 893 ms 460 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 392 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 388 ms 560 KB Output is correct
12 Correct 700 ms 344 KB Output is correct
13 Correct 728 ms 848 KB Output is correct
14 Correct 1383 ms 600 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 -