oj.uz

Submission #1117124

# Submission time Handle Problem Language Result Execution time Memory
1117124 2024-11-22T20:48:00 Z ThegeekKnight16 Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 44408 KB 
#include <bits/stdc++.h>
using namespace std;
#include "rainbow.h"
set<pair<int, int>> relevantes;
set<pair<int, int>> agua;
int dx[] = {1,-1,0,0,1,-1,1,-1};
int dy[] = {0,0,1,-1,1,1,-1,-1};

void dfs(int x, int y, set<pair<int, int>> &marc, int ar, int ac, int br, int bc)
{
    marc.emplace(x, y);
    // cerr << x << " " << y << " ok " << '\n';

    for (int k = 0; k < 4; k++)
    {
        int hx = x + dx[k], hy = y + dy[k];
        if (hx < ar || hy < ac || hx > br || hy > bc) continue;
        if (agua.count(make_pair(hx, hy)) || marc.count(make_pair(hx, hy))) continue;
        if (!relevantes.count(make_pair(hx, hy))) continue;
        dfs(hx, hy, marc, ar, ac, br, bc);
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) 
{
    agua.emplace(sr, sc); relevantes.emplace(sr, sc);
    for (int k = 0; k < 8; k++) relevantes.emplace(sr+dx[k], sc+dy[k]);
    // cerr << "snake: " << '\n';
    // cerr << "sr: " << sr << ", sc: " << sc << '\n';

    for (int i = 0; i < M; i++)
    {
        if (S[i] == 'N') sr--;
        else if (S[i] == 'S') sr++;
        else if (S[i] == 'E') sc++;
        else sc--;
        agua.emplace(sr, sc); relevantes.emplace(sr, sc);
        // cerr << "sr: " << sr << ", sc: " << sc << '\n';
        for (int k = 0; k < 8; k++) relevantes.emplace(sr+dx[k], sc+dy[k]);
    }
}

int colour(int ar, int ac, int br, int bc) 
{
    set<pair<int, int>> marc; int numAgua = 0; int resp = 0;
    for (auto [x, y] : relevantes)
    {
        if (x < ar || y < ac || x > br || y > bc) continue;
        if (agua.count(make_pair(x, y))) {numAgua++; continue;}
        if (marc.count(make_pair(x, y))) continue;

        dfs(x, y, marc, ar, ac, br, bc); resp++;
        // cerr << "thats comp" << '\n';
    }

    // cerr << "numAgua: " << numAgua << '\n'; 
    if (numAgua == 0) return 1;
    return resp;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Execution timed out 3061 ms 16456 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 336 KB Output is correct
2 Correct 280 ms 31608 KB Output is correct
3 Correct 264 ms 31780 KB Output is correct
4 Correct 411 ms 44408 KB Output is correct
5 Correct 202 ms 23112 KB Output is correct
6 Correct 63 ms 3188 KB Output is correct
7 Correct 96 ms 7548 KB Output is correct
8 Correct 144 ms 17992 KB Output is correct
9 Correct 113 ms 15148 KB Output is correct
10 Incorrect 52 ms 3920 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -