Submission #200314

#	Time	Username	Problem	Language	Result	Execution time	Memory
200314		deepwork	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	34 ms	1144 KiB

rainbow

#include "rainbow.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 50;

int n, m, k;
int sx, sy;
string s;
bool bad[N][N];

int p[N*N];
int sz[N*N];
int was[N*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 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];    
    markBads();
}

int colour(int ar, int ac, int br, int bc) {
    ar--;
    ac--;
    br--;
    bc--;
    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);
        }
    }
    int ans = 0;
    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: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26