oj.uz

Submission #403327

# Submission time Handle Problem Language Result Execution time Memory
403327 2021-05-13T03:53:07 Z wiwiho Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 1048580 KB 
#include "rainbow.h"

#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

using pii = pair<int, int>;

vector<vector<bool>> g;
vector<vector<int>> vst;

int n, m;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R; m = C;
    g.resize(n + 2, vector<bool>(m + 2));
    for(int i = 1; i <= m; i++){
        g[0][i] = g[n + 1][i] = true;
    }
    for(int i = 1; i <= n; i++){
        g[i][0] = g[i][m + 1] = true;
    }

    g[sr][sc] = true;
    for(int i = 0; i < M; i++){
        if(S[i] == 'N') sr--;
        else if(S[i] == 'S') sr++;
        else if(S[i] == 'W') sc--;
        else sc++;
        g[sr][sc] = true;
    }

    //for(int i = 0; i <= n + 1; i++) printv(g[i], cerr);
}

vector<pii> dir = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1)};

void bfs(int sx, int sy, int ar, int ac, int br, int bc){
    queue<pii> q;
    q.push(mp(sx, sy));
    vst[sx][sy] = true;
    while(!q.empty()){
        int x = q.front().F, y = q.front().S;
        q.pop();
        for(pii d : dir){
            int nx = x + d.F, ny = y + d.S;
            if(g[nx][ny] || vst[nx][ny]) continue;
            if(nx < ar || br < nx || ny < ac || bc < ny) continue;
            vst[nx][ny] = true;
            q.push(mp(nx, ny));
        }
    }
}

int colour(int ar, int ac, int br, int bc) {

    vst.clear();
    vst.resize(n + 2, vector<int>(m + 2));

    int ans = 0;
    for(int i = ar; i <= br; i++){
        for(int j = ac; j <= bc; j++){
            if(g[i][j] || vst[i][j]) continue;
            ans++;
            bfs(i, j, ar, ac, br, bc);
        }
    }

    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 312 KB Output is correct
2 Correct 12 ms 344 KB Output is correct
3 Correct 26 ms 340 KB Output is correct
4 Correct 26 ms 332 KB Output is correct
5 Correct 11 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 23 ms 348 KB Output is correct
12 Correct 19 ms 344 KB Output is correct
13 Correct 14 ms 336 KB Output is correct
14 Correct 24 ms 352 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 3058 ms 5844 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 204 KB Output is correct
2 Runtime error 599 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 312 KB Output is correct
2 Correct 12 ms 344 KB Output is correct
3 Correct 26 ms 340 KB Output is correct
4 Correct 26 ms 332 KB Output is correct
5 Correct 11 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 23 ms 348 KB Output is correct
12 Correct 19 ms 344 KB Output is correct
13 Correct 14 ms 336 KB Output is correct
14 Correct 24 ms 352 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3092 ms 4892 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 312 KB Output is correct
2 Correct 12 ms 344 KB Output is correct
3 Correct 26 ms 340 KB Output is correct
4 Correct 26 ms 332 KB Output is correct
5 Correct 11 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 23 ms 348 KB Output is correct
12 Correct 19 ms 344 KB Output is correct
13 Correct 14 ms 336 KB Output is correct
14 Correct 24 ms 352 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3092 ms 4892 KB Time limit exceeded
19 Halted 0 ms 0 KB -