Submission #1117183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117183		hyakup	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	3072 ms	89672 KiB

rainbow

#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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26