oj.uz

Submission #1089992

# Submission time Handle Problem Language Result Execution time Memory
1089992 2024-09-17T13:48:00 Z alexander707070 Land of the Rainbow Gold (APIO17_rainbow) C++14
24 / 100
 1399 ms 258060 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--){
            if(table[1][i]==-1)table[1][i]=comps+1;
            if(table[2][i]==-1)table[2][i]=comps+1;

            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(2, 10 ,2,2, 11,"NEEESEENEEE");

    cout<<colour(1,2,2,7)<<"\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:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
rainbow.cpp:138:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 348 KB Output is correct
2 Correct 638 ms 612 KB Output is correct
3 Correct 114 ms 344 KB Output is correct
4 Correct 180 ms 540 KB Output is correct
5 Correct 897 ms 592 KB Output is correct
6 Correct 0 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 393 ms 556 KB Output is correct
12 Correct 721 ms 580 KB Output is correct
13 Correct 729 ms 600 KB Output is correct
14 Correct 1399 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Incorrect 1 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 1 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 344 KB Output is correct
2 Correct 541 ms 98548 KB Output is correct
3 Correct 502 ms 98388 KB Output is correct
4 Correct 457 ms 79700 KB Output is correct
5 Correct 236 ms 49492 KB Output is correct
6 Correct 152 ms 33432 KB Output is correct
7 Correct 315 ms 47192 KB Output is correct
8 Correct 85 ms 17664 KB Output is correct
9 Correct 75 ms 15440 KB Output is correct
10 Correct 31 ms 3920 KB Output is correct
11 Correct 55 ms 12372 KB Output is correct
12 Correct 126 ms 26332 KB Output is correct
13 Correct 95 ms 26348 KB Output is correct
14 Correct 81 ms 20048 KB Output is correct
15 Correct 80 ms 21584 KB Output is correct
16 Correct 133 ms 27104 KB Output is correct
17 Correct 119 ms 27220 KB Output is correct
18 Correct 169 ms 44036 KB Output is correct
19 Correct 655 ms 152656 KB Output is correct
20 Correct 515 ms 105888 KB Output is correct
21 Correct 166 ms 20624 KB Output is correct
22 Correct 159 ms 18512 KB Output is correct
23 Correct 277 ms 64592 KB Output is correct
24 Correct 420 ms 91988 KB Output is correct
25 Correct 537 ms 93012 KB Output is correct
26 Correct 483 ms 104016 KB Output is correct
27 Correct 1200 ms 258060 KB Output is correct
28 Correct 439 ms 87888 KB Output is correct
29 Correct 326 ms 52820 KB Output is correct
30 Correct 340 ms 55608 KB Output is correct
31 Correct 1068 ms 229204 KB Output is correct
32 Correct 1170 ms 240944 KB Output is correct
33 Correct 1174 ms 240976 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 348 KB Output is correct
2 Correct 638 ms 612 KB Output is correct
3 Correct 114 ms 344 KB Output is correct
4 Correct 180 ms 540 KB Output is correct
5 Correct 897 ms 592 KB Output is correct
6 Correct 0 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 393 ms 556 KB Output is correct
12 Correct 721 ms 580 KB Output is correct
13 Correct 729 ms 600 KB Output is correct
14 Correct 1399 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Incorrect 1 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 109 ms 348 KB Output is correct
2 Correct 638 ms 612 KB Output is correct
3 Correct 114 ms 344 KB Output is correct
4 Correct 180 ms 540 KB Output is correct
5 Correct 897 ms 592 KB Output is correct
6 Correct 0 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 393 ms 556 KB Output is correct
12 Correct 721 ms 580 KB Output is correct
13 Correct 729 ms 600 KB Output is correct
14 Correct 1399 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -