Submission #408579

#	Time	Username	Problem	Language	Result	Execution time	Memory
408579		abc864197532	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	3082 ms	1048580 KiB

rainbow

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cerr << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv() {}
};
#ifdef Doludu
#define test(args...) info(), abc("[" + string(#args) + "]", args)
#define owo
#include "rainbow-grader.cpp"
#else
#define test(args...)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
// const int mod = 998244353, N = 1000001, logN = 20, K = 111;

vv <bool> area;
int n, m;

void init(int _n, int _m, int r, int c, int k, char *s) {
    r--, c--;
    n = _n, m = _m;
    area = vv<bool>(n, m, false);
    area[r][c] = true;
    for (int i = 0; i < k; ++i) {
        if (s[i] == 'W') c--;
        if (s[i] == 'E') c++;
        if (s[i] == 'N') r--;
        if (s[i] == 'S') r++;
        area[r][c] = true;
    }
}

int colour(int l1, int r1, int l2, int r2) {
    l1--, r1--;
    vv <bool> vis = area;
    int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
    function<void(int, int)> bfs = [&](int a, int b) {
        queue <pii> q;
        q.emplace(a, b);
        vis[a][b] = true;
        while (!q.empty()) {
            int x, y;
            tie(x, y) = q.front(); q.pop();
            test(x, y);
            for (int k = 0; k < 4; ++k) {
                int nx = x + dx[k], ny = y + dy[k];
                if (l1 <= nx && nx < l2 && r1 <= ny && ny < r2) if (!vis[nx][ny]) {
                    vis[nx][ny] = true;
                    q.emplace(nx, ny);
                }
            }
        }
    };
    int ans = 0;
    for (int i = l1; i < l2; ++i) for (int j = r1; j < r2; ++j) {
        if (vis[i][j]) continue;
        bfs(i, j);
        ans++;
    }
    return ans;
}

/*
6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3
 */

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