oj.uz

Submission #1089984

# Submission time Handle Problem Language Result Execution time Memory
1089984 2024-09-17T13:40:54 Z alexander707070 Land of the Rainbow Gold (APIO17_rainbow) C++14
24 / 100
 1406 ms 259584 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[1007][1007];

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 i=1;i<=n;i++){
        for(int f=1;f<=m;f++){
            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 105 ms 344 KB Output is correct
2 Correct 618 ms 600 KB Output is correct
3 Correct 109 ms 348 KB Output is correct
4 Correct 192 ms 552 KB Output is correct
5 Correct 868 ms 848 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 0 ms 352 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 389 ms 572 KB Output is correct
12 Correct 683 ms 848 KB Output is correct
13 Correct 717 ms 848 KB Output is correct
14 Correct 1406 ms 656 KB Output is correct
15 Correct 0 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 0 ms 348 KB Output is correct
2 Correct 538 ms 99920 KB Output is correct
3 Correct 457 ms 99944 KB Output is correct
4 Correct 462 ms 81232 KB Output is correct
5 Correct 262 ms 51028 KB Output is correct
6 Correct 155 ms 35032 KB Output is correct
7 Correct 319 ms 48724 KB Output is correct
8 Correct 81 ms 18052 KB Output is correct
9 Correct 70 ms 15540 KB Output is correct
10 Correct 31 ms 3920 KB Output is correct
11 Correct 55 ms 12772 KB Output is correct
12 Correct 120 ms 27728 KB Output is correct
13 Correct 96 ms 27728 KB Output is correct
14 Correct 85 ms 21464 KB Output is correct
15 Correct 86 ms 23104 KB Output is correct
16 Correct 134 ms 28752 KB Output is correct
17 Correct 126 ms 28752 KB Output is correct
18 Correct 173 ms 45600 KB Output is correct
19 Correct 708 ms 154024 KB Output is correct
20 Correct 549 ms 107500 KB Output is correct
21 Correct 181 ms 20904 KB Output is correct
22 Correct 168 ms 18768 KB Output is correct
23 Correct 294 ms 64592 KB Output is correct
24 Correct 437 ms 92244 KB Output is correct
25 Correct 573 ms 94440 KB Output is correct
26 Correct 500 ms 105556 KB Output is correct
27 Correct 1212 ms 259584 KB Output is correct
28 Correct 440 ms 89504 KB Output is correct
29 Correct 305 ms 54412 KB Output is correct
30 Correct 345 ms 57428 KB Output is correct
31 Correct 1077 ms 230672 KB Output is correct
32 Correct 1219 ms 242512 KB Output is correct
33 Correct 1168 ms 242516 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 344 KB Output is correct
2 Correct 618 ms 600 KB Output is correct
3 Correct 109 ms 348 KB Output is correct
4 Correct 192 ms 552 KB Output is correct
5 Correct 868 ms 848 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 0 ms 352 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 389 ms 572 KB Output is correct
12 Correct 683 ms 848 KB Output is correct
13 Correct 717 ms 848 KB Output is correct
14 Correct 1406 ms 656 KB Output is correct
15 Correct 0 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 105 ms 344 KB Output is correct
2 Correct 618 ms 600 KB Output is correct
3 Correct 109 ms 348 KB Output is correct
4 Correct 192 ms 552 KB Output is correct
5 Correct 868 ms 848 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 452 KB Output is correct
9 Correct 0 ms 352 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 389 ms 572 KB Output is correct
12 Correct 683 ms 848 KB Output is correct
13 Correct 717 ms 848 KB Output is correct
14 Correct 1406 ms 656 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -