oj.uz

Submission #1089978

# Submission time Handle Problem Language Result Execution time Memory
1089978 2024-09-17T13:05:10 Z alexander707070 Land of the Rainbow Gold (APIO17_rainbow) C++14
35 / 100
 3000 ms 258132 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;

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]);
    }
}

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;

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 348 KB Output is correct
2 Correct 619 ms 604 KB Output is correct
3 Correct 107 ms 348 KB Output is correct
4 Correct 181 ms 344 KB Output is correct
5 Correct 876 ms 844 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 392 ms 544 KB Output is correct
12 Correct 683 ms 344 KB Output is correct
13 Correct 709 ms 852 KB Output is correct
14 Correct 1382 ms 628 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 3011 ms 60516 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 510 ms 98384 KB Output is correct
3 Correct 439 ms 98388 KB Output is correct
4 Correct 431 ms 79440 KB Output is correct
5 Correct 228 ms 49492 KB Output is correct
6 Correct 143 ms 33560 KB Output is correct
7 Correct 299 ms 47044 KB Output is correct
8 Correct 78 ms 17764 KB Output is correct
9 Correct 65 ms 15444 KB Output is correct
10 Correct 30 ms 3924 KB Output is correct
11 Correct 53 ms 12308 KB Output is correct
12 Correct 128 ms 26196 KB Output is correct
13 Correct 97 ms 26268 KB Output is correct
14 Correct 81 ms 20000 KB Output is correct
15 Correct 83 ms 21584 KB Output is correct
16 Correct 132 ms 27000 KB Output is correct
17 Correct 126 ms 27216 KB Output is correct
18 Correct 170 ms 44084 KB Output is correct
19 Correct 653 ms 152508 KB Output is correct
20 Correct 512 ms 106068 KB Output is correct
21 Correct 180 ms 20560 KB Output is correct
22 Correct 165 ms 18512 KB Output is correct
23 Correct 268 ms 64596 KB Output is correct
24 Correct 411 ms 91852 KB Output is correct
25 Correct 515 ms 93008 KB Output is correct
26 Correct 471 ms 103984 KB Output is correct
27 Correct 1137 ms 258132 KB Output is correct
28 Correct 431 ms 87932 KB Output is correct
29 Correct 325 ms 52816 KB Output is correct
30 Correct 361 ms 55600 KB Output is correct
31 Correct 1073 ms 229108 KB Output is correct
32 Correct 1177 ms 240988 KB Output is correct
33 Correct 1099 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 619 ms 604 KB Output is correct
3 Correct 107 ms 348 KB Output is correct
4 Correct 181 ms 344 KB Output is correct
5 Correct 876 ms 844 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 392 ms 544 KB Output is correct
12 Correct 683 ms 344 KB Output is correct
13 Correct 709 ms 852 KB Output is correct
14 Correct 1382 ms 628 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3053 ms 14180 KB Time limit exceeded
19 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 619 ms 604 KB Output is correct
3 Correct 107 ms 348 KB Output is correct
4 Correct 181 ms 344 KB Output is correct
5 Correct 876 ms 844 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 392 ms 544 KB Output is correct
12 Correct 683 ms 344 KB Output is correct
13 Correct 709 ms 852 KB Output is correct
14 Correct 1382 ms 628 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3053 ms 14180 KB Time limit exceeded
19 Halted 0 ms 0 KB -