oj.uz

Submission #1117183

# Submission time Handle Problem Language Result Execution time Memory
1117183 2024-11-22T21:33:54 Z hyakup Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 89672 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
#define pii pair<int, int>

const int maxn = 2e5 + 10;
const int inf = 1e9;

map<int, map<int, bool>> marc;
int n, m, q;

int di[] = { 0, 1, 0, -1 };
int dj[] = { 1, 0, -1, 0 };
int linha1, linha2, coluna1, coluna2;


set<pair<int, int>> proibidos,  todos;
set<int> linha[maxn], coluna[maxn];

bool find( set<pii>& s, pii p ){ return s.find(p) != s.end(); }
bool in_bounds( int i, int j ){
    if( find( proibidos, pii( i, j ) ) ) return false;
    return linha1 <= i && i <= linha2 && coluna1 <= j && j <= coluna2;
}
void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    linha1 = 1; coluna1 = 1; linha2 = n; coluna2 = m;
    // //bug(R);

    vector<pair<int, int>> path;

    proibidos.insert({ sr, sc });
    path.push_back({ sr, sc });
    for( int i = 0; i < M; i++ ){
        char c = S[i];
        if( c == 'N' ) sr--;
        if( c == 'S' ) sr++;
        if( c == 'W' ) sc--;
        if( c == 'E' ) sc++;

        proibidos.insert({ sr, sc });
        linha[sr].insert(sc);
        coluna[sc].insert(sr);
        path.push_back({ sr, sc });
    }

    for( auto [i, j] : proibidos ){
        for( int slai = -1; slai <= 1; slai ++ ){
            for( int slaj = -1; slaj <= 1; slaj++ ){
                pii novo( i + slai, j + slaj );
                if( !find(proibidos, novo) && in_bounds( novo.first, novo.second ) ){
                    linha[novo.first].insert(novo.second);
                    coluna[novo.second].insert(novo.first);
                    todos.insert(novo);
                }

            }
        }
    }

}

void dfs( int i, int j ){

    // cout << " CUR " << i << " " << j << endl;
    marc[i][j] = true;
    auto down = coluna[j].upper_bound(i);

    if( down != coluna[j].end() && marc[*down][j] == false && in_bounds( *down, j ) ) dfs( *down, j );
    if( prev(down) != coluna[j].begin() && marc[*prev(prev(down))][j] == false && in_bounds( *prev(prev(down)), j) ) dfs( *prev(prev(down)), j );
    // cerr  << " sla " << endl;
    auto right = linha[i].upper_bound(j);
    //bug(*right);
    if( right != linha[i].end() && marc[i][*right] == false && in_bounds( i, *right ) ) dfs( i, *right );
    if( prev(right) != linha[i].begin() && marc[i][*prev(prev(right))] == false && in_bounds( i, *prev(prev(right)) ) ) dfs( i, *prev(prev(right)) );
}

int colour(int ar, int ac, int br, int bc) {
    linha1 = ar; coluna1 = ac; linha2 = br; coluna2 = bc;

    int resp = 0;

    for( auto [i, j] : todos ) marc[i][j] = false; 

    for( auto [i, j] : todos ){
        //bug(i);
        //bug(j);
        // cout << endl;
        if( in_bounds( i, j ) && !marc[i][j] ){ resp++; dfs( i, j ); }
    }
    return resp;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19192 KB Output is correct
2 Correct 4 ms 19040 KB Output is correct
3 Execution timed out 3072 ms 42920 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19024 KB Output is correct
2 Correct 490 ms 78032 KB Output is correct
3 Correct 517 ms 87464 KB Output is correct
4 Correct 466 ms 89672 KB Output is correct
5 Correct 329 ms 67596 KB Output is correct
6 Incorrect 43 ms 24960 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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