oj.uz

Submission #983458

# Submission time Handle Problem Language Result Execution time Memory
983458 2024-05-15T13:13:11 Z stegatxins0 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 13732 KB 
#include <bits/stdc++.h>
using namespace std;
#include "rainbow.h"

#ifdef DEBUG
#include "debug.cpp"
#else
#define dbg(...)
#define dbgarr(...)
#endif

const int mxN = 1001;
bool river[mxN][mxN], visited[mxN][mxN];

// {{{ HASHMAP
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

struct chash {
    const uint64_t C = (long long)(4e18 * acos(0)) | 71;
	const uint32_t RANDOM =
	    chrono::steady_clock::now().time_since_epoch().count();
	size_t operator()(uint64_t x) const {
		return __builtin_bswap64((x ^ RANDOM) * C);
	}
};
// }}}

int R,C;

void init(int _R, int _C, int sr, int sc, int M, char *S) {
    R = _R, C = _C;
    memset(river,0,sizeof(river));
    int y = sr, x = sc;
    gp_hash_table<char, pair<int,int>> mp; // dy, dx;
    // unordered_map<char,pair<int,int>> mp;

    mp['N'] = {-1, 0};
    mp['S'] = {1, 0};
    mp['W'] = {0, -1};
    mp['E'] = {0, 1};

    river[y][x] = 1;
    for(int i=0; i<M; i++){
        y += mp[S[i]].first;
        x += mp[S[i]].second;
        river[y][x] = 1;
        dbg(y,x);
    }
}

const int dy[4] = {-1, 1, 0, 0};
const int dx[4] = {0, 0, -1, 1};
void dfs(int y, int x, int ar, int ac, int br, int bc){
    visited[y][x] = 1;

    for(int i=0; i<4; i++){
        int newy = y + dy[i];
        int newx = x + dx[i];
        if(newy >= ar && newx >= ac && newy <= br && newx <= bc && !river[newy][newx] && !visited[newy][newx]){
            dfs(newy, newx, ar, ac, br, bc);
        }
    }


}


int colour(int ar, int ac, int br, int bc) {
    memset(visited,0,sizeof(visited));
    int ans = 0;
    for(int y=ar; y<=br; y++){
        for(int x=ac; x<=bc; x++){
            if(!river[y][x] && !visited[y][x]){
                dfs(y,x,ar,ac,br,bc);
                ans++;
            }
        }
    }

    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2396 KB Output is correct
2 Correct 20 ms 2648 KB Output is correct
3 Correct 27 ms 2396 KB Output is correct
4 Correct 28 ms 2560 KB Output is correct
5 Correct 23 ms 2648 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2152 KB Output is correct
11 Correct 26 ms 2396 KB Output is correct
12 Correct 23 ms 2396 KB Output is correct
13 Correct 21 ms 2396 KB Output is correct
14 Correct 18 ms 2392 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 2 ms 2652 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2396 KB Output is correct
2 Correct 20 ms 2648 KB Output is correct
3 Correct 27 ms 2396 KB Output is correct
4 Correct 28 ms 2560 KB Output is correct
5 Correct 23 ms 2648 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2152 KB Output is correct
11 Correct 26 ms 2396 KB Output is correct
12 Correct 23 ms 2396 KB Output is correct
13 Correct 21 ms 2396 KB Output is correct
14 Correct 18 ms 2392 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Execution timed out 3049 ms 11384 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2396 KB Output is correct
2 Correct 20 ms 2648 KB Output is correct
3 Correct 27 ms 2396 KB Output is correct
4 Correct 28 ms 2560 KB Output is correct
5 Correct 23 ms 2648 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2152 KB Output is correct
11 Correct 26 ms 2396 KB Output is correct
12 Correct 23 ms 2396 KB Output is correct
13 Correct 21 ms 2396 KB Output is correct
14 Correct 18 ms 2392 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Execution timed out 3049 ms 11384 KB Time limit exceeded
19 Halted 0 ms 0 KB -