Submission #200367

#	Time	Username	Problem	Language	Result	Execution time	Memory
200367		deepwork	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	1074 ms	1048580 KiB

rainbow

#include "rainbow.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e5;

int n, m, k;
int sx, sy;
string s;
vector<vector<int>> bad;

int p[N];
int sz[N];
int was[N];

int cur;
int id[N];

int get(int u) {
    return (p[u] == u ? u : p[u] = get(p[u]));
}

void unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v)
        return;
    if (sz[u] > sz[v])
        swap(u, v);
    p[u] = v;
    sz[v] += sz[u];
}

void markBads() {
    int x = sx, y = sy;
    bad[sx][sy] = true;
    for (char c : s) {
        if (c == 'N')
            x--;
        if (c == 'S')
            x++;
        if (c == 'W')
            y--;
        if (c == 'E')
            y++;
        bad[x][y] = true;
    }
}

void makeUnions() {
    fill(id, id+N, -1);
    for (int j = 0; j < m; j++) {
        p[j] = j;
        sz[j] = 1;
        p[m+j] = m+j;
        sz[m+j] = 1;
    }
    for (int j = 0; j < m; j++) {
        if (!bad[0][j] && !bad[1][j])
            unite(j, m+j);
        if (j+1 < m && !bad[0][j] && !bad[0][j+1])
            unite(j, j+1);
        if (j+1 < m && !bad[1][j] && !bad[1][j+1])
            unite(m+j, m+j+1);            
    }
    for (int i : {0, 1})
        for (int j = 0; j < m; j++)
            if (id[get(i*m+j)] == -1)
                id[get(i*m+j)] = cur++;
    int uni = -1;
    for (int j = 0; j < m; j++) {
        if (!bad[0][j]) 
            uni = max(uni, get(j));
        if (!bad[1][j])
            uni = max(uni, get(m+j));
        if (bad[0][j])
            id[j] = uni;
        if (bad[1][j])
            id[m+j] = uni;
    }
    uni = cur-1;
    for (int j = m-1; j >= 0; j--) {
        if (!bad[0][j])
            uni = min(uni, id[j]); 
        if (!bad[1][j])
            uni = min(uni, id[m+j]);
        if (bad[0][j])
            id[j] = uni;
        if (bad[1][j])
            id[m+j] = uni;
    }
}       

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R;
    m = C;
    sr--;
    sc--;
    sx = sr;
    sy = sc;
    s.clear();
    for (int i = 0; i < M; i++)
        s += S[i];
    bad.resize(n, vector<int>(m));  
    markBads();
    if (n == 2)
        makeUnions();
}

int colour(int ar, int ac, int br, int bc) {
    ar--;
    ac--;
    br--;
    bc--;
    int ans = 0;
    if (n == 2) {
        ans = id[br*m+bc]-id[ar*m+ac]+1;   
    } else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p[i*m+j] = i*m+j;
                sz[i*m+j] = 1;
            }
        }
        for (int i = ar; i <= br; i++) {    
            for (int j = ac; j <= bc; j++) {
                if (j+1 <= bc && !bad[i][j] && !bad[i][j+1])            
                    unite(i*m+j, i*m+j+1);
                if (i+1 <= br && !bad[i][j] && !bad[i+1][j])
                    unite(i*m+j, (i+1)*m+j);
            }
        }
        fill(was, was+n*m, false);
        for (int i = ar; i <= br; i++) {
            for (int j = ac; j <= bc; j++) {
                if (bad[i][j])
                    continue;
                ans += !was[get(i*m+j)];
                was[get(i*m+j)] = true;
            }
        }
    }                      
    return ans;
}

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