제출 #904314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
904314		shezitt	무지개나라 (APIO17_rainbow)	C++14	23 / 100	3052 ms	103956 KiB

rainbow

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int,int>
#define dbg(x) cerr << #x << ": " << x << endl
#define raya cerr << "=================" << endl
#define pb push_back

const int N = 2e5+5;
vector<vector<int>> grid;
int rows, cols;

map<char,ii> to = {{'N', {-1, 0}}, {'S', {1, 0}}, {'W', {0, -1}}, {'E', {0, 1}}};

int arriba[N], abajo[N], ambos[N];

set<ii> nodes;
set<pair<ii,ii>> edges;

vector<ii> getNodes(int row, int col){
    vector<ii> res;
    res.pb({row, col});
    res.pb({row+1, col});
    res.pb({row, col+1});
    res.pb({row+1, col+1});
    return res;
}

void insertNodes(int row, int col){
    nodes.insert({row, col});
    nodes.insert({row+1, col});
    nodes.insert({row, col+1});
    nodes.insert({row+1, col+1});

    edges.insert({{row, col}, {row+1, col}});
    edges.insert({{row, col}, {row, col+1}});
    edges.insert({{row+1, col}, {row+1, col+1}});
    edges.insert({{row, col+1}, {row+1, col+1}});
    
}

set<ii> nodosSnake;

void init(int R, int C, int sr, int sc, int M, char *s){
    rows = R;
    cols = C;
    sr--, sc--;

    if(rows == 2){
        grid.assign(3, vector<int>(cols+1, 0));
    } else if(rows*cols <= 1e6) {
        grid.assign(rows+1, vector<int>(cols+1, 0));
    }

    if(rows*cols <= 1e6){
        ii pos = {sr, sc};
        grid[pos.first][pos.second] = 1;
        for(int i=0; i<M; ++i){
            char c = s[i];
            pos.first += to[c].first;
            pos.second += to[c].second;
            grid[pos.first][pos.second] = 1;
        }
    }

    if(rows == 2){
        // subtask 2
        arriba[0] = (grid[0][0] == 0);
        abajo[0] = (grid[1][0] == 0);
        for(int i=1; i<cols; ++i){
            arriba[i] = (grid[0][i-1] == 1 && grid[0][i] == 0);
            abajo[i] = (grid[1][i-1] == 1 && grid[1][i] == 0);
        }
        for(int i=1; i<cols; ++i){
            arriba[i] += arriba[i-1];
            abajo[i] += abajo[i-1];
        }
        // ambos
        ambos[0] = (grid[0][0] == 0 && grid[1][0] == 0);
        for(int i=1; i<cols; ++i){
            if(grid[0][i-1] == 1 or grid[1][i-1] == 1){
                ambos[i] = (grid[0][i] == 0 && grid[1][i] == 0);
            }
        }
        for(int i=1; i<cols; ++i){
            ambos[i] += ambos[i-1];
        }
    }

    // subtask 3
    ii pos = {sr, sc};
    nodosSnake.insert({sr, sc});
    for(int i=0; i<M; ++i){
        char c = s[i];
        pos.first += to[c].first;
        pos.second += to[c].second;
        nodosSnake.insert(pos);
    }

}

void clear(){
    for(int i=0; i<rows; ++i){
        for(int j=0; j<cols; ++j){
            if(grid[i][j] == 2) grid[i][j] = 0;
        }
    }
}

vector<ii> mov = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

void dfs(int i, int j, int ar, int ac, int br, int bc){
    for(auto tmp : mov){
        int ni = i + tmp.first;
        int nj = j + tmp.second;
        if(ni >= ar && ni <= br && nj >= ac && nj <= bc && grid[ni][nj] == 0){
            grid[ni][nj] = 2;
            dfs(ni, nj, ar, ac, br, bc);
        }
    }
}

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

    ar--, ac--;
    br--, bc--;

    if(rows == 2){
        // subtask 2
        if(ar+1 == br){
            // ambos
            int res = arriba[bc] + abajo[bc];
            int quitar = ambos[bc];
            if(ac > 0){
                res -= arriba[ac-1] - (grid[0][ac-1] == 0 && grid[0][ac] == 0);
                res -= abajo[ac-1] - (grid[1][ac-1] == 0 && grid[1][ac] == 0);
                quitar -= ambos[ac-1] - (grid[0][ac-1] == 0 && grid[0][ac] == 0 && grid[1][ac-1] == 0 && grid[1][ac] == 0);
            }
            res -= quitar;
            return res;
        }
        // arriba
        if(ar == 0){
            int res = arriba[bc];
            if(ac > 0){
                res -= arriba[ac-1] - (grid[0][ac-1] == 0 && grid[0][ac] == 0);
            }
            return res;
        }
        // abajo
        assert(ar == 1);
        int res = abajo[bc];
        if(ac > 0){
            res -= abajo[ac-1] - (grid[1][ac-1] == 0 && grid[1][ac] == 0);
        }
        return res;
    }

    if(rows*cols <= 1e6){
        // subtask 1
        int ans = 0;
        for(int i=ar; i<=br; ++i){
            for(int j=ac; j<=bc; ++j){
                if(grid[i][j] == 0){
                    ans++;
                    grid[i][j] = 2;
                    dfs(i, j, ar, ac, br, bc);
                }
            }
        }
        clear();
        return ans;
    }

    // only one query (subtask 3)
    int tamSnake = 0;
    for(auto node : nodosSnake){
        if(node.first >= ar && node.first <= br && node.second >= ac && node.second <= bc){
            tamSnake++;
            insertNodes(node.first, node.second);
        }
    }

    bool ok = 0;
    for(int col=ac; col<=bc; ++col){
        vector<ii> tmp = getNodes(ar-1, col);
        for(auto node : tmp){
            ok |= nodes.count(node);
        }
        tmp = getNodes(br+1, col);
        for(auto node : tmp){
            ok |= nodes.count(node);
        }
    }

    for(int row=ar; row<=br; ++row){
        vector<ii> tmp = getNodes(row, ac-1);
        for(auto node : tmp){
            ok |= nodes.count(node);
        }
        tmp = getNodes(row, bc+1);
        for(auto node : tmp){
            ok |= nodes.count(node);
        }
    }

    if(ok){
        // include the border
        for(int col=ac; col<=bc; ++col){
            insertNodes(ar-1, col);
            insertNodes(br+1, col);
        }
        for(int row=ar; row<=br; ++row){
            insertNodes(row, ac-1);
            insertNodes(row, bc+1);
        }
    }

    int ans = 2 - (int)nodes.size() + (int)edges.size() - ok;
    // quitar snake size
    ans -= tamSnake;
    // quitar border size si es que fue incluido
    if(ok){
        ans -= (br-ar+1) * 2 + (bc-ac+1) * 2;
    }

    return ans;

    
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26