oj.uz

Submission #545834

# Submission time Handle Problem Language Result Execution time Memory
545834 2022-04-05T14:26:29 Z Monarchuwu Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 34284 KB 
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 2e5 + 8;
const int dr[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dc[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int r, c, m, q, sr, sc;
int num[256];
string s;

namespace subtask1 {
    bool vis_init[52][52], vis[52][52];
    void init() {
        vis_init[sr][sc] = true;
        for (char c : s) {
            sr += dr[num[c]];
            sc += dc[num[c]];
            vis_init[sr][sc] = true;
        }
    }
    void dfs(int i, int j) {
        vis[i][j] = true;
        for (int k = 0, i2, j2; k < 4; ++k) {
            i2 = i + dr[k], j2 = j + dc[k];
            if (!vis[i2][j2]) dfs(i2, j2);
        }
    }
    int solve(int ar, int ac, int br, int bc) {
        int m = br - ar + 1, n = bc - ac + 1;
        for (int i = 1; i <= m; ++i) vis[i][0] = vis[i][n + 1] = true;
        for (int j = 1; j <= n; ++j) vis[0][j] = vis[m + 1][j] = true;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                vis[i][j] = vis_init[i + ar - 1][j + ac - 1];

        int cnt(0);
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                if (!vis[i][j]) dfs(i, j), ++cnt;
        return cnt;
    }
}

namespace subtask2 {
    bool vis[4][N];
    int prf[4][N];
    void init() {
        vis[1][0] = vis[2][0] = vis[sr][sc] = true;
        for (char c : s) {
            sr += dr[num[c]];
            sc += dc[num[c]];
            vis[sr][sc] = true;
        }
        for (int i = 1; i <= c; ++i) {
            prf[1][i] = prf[1][i - 1] + (vis[1][i - 1] && !vis[1][i]);
            prf[2][i] = prf[2][i - 1] + (vis[2][i - 1] && !vis[2][i]);
            prf[3][i] = prf[3][i - 1] + (vis[1][i - 1] && vis[2][i - 1] && (!vis[1][i] || !vis[2][i]));
        }
    }
    int solve(int ar, int ac, int br, int bc) {
        if (ar == br) {
            return prf[ar][bc] - prf[ar][ac - 1] + (!vis[ar][ac - 1] && !vis[ar][ac]);
        }
        else {
            return prf[3][bc] - prf[3][ac - 1] + ((!vis[1][ac - 1] || !vis[2][ac - 1]) && (!vis[1][ac] || !vis[2][ac]));
        }
    }
}

namespace subtask3 {
    set<pii> vis, arr_set;
    map<pii, int> mp;
    pii a[N << 2];
    void init() {
        vis.emplace(sr, sc);
        for (char c : s) {
            sr += dr[num[c]];
            sc += dc[num[c]];
            vis.emplace(sr, sc);
        }

        arr_set = vis;
        for (pii x : arr_set) {
            for (int k = 0; k < 8; ++k) {
                pii p(x.ff + dr[k], x.ss + dc[k]);
                if (1 <= p.ff && p.ff <= r && 1 <= p.ss && p.ss <= c && vis.insert(p).ss)
                    a[mp[p] = mp.size() + 1] = p;
            }
        }
    }

    int par[N << 2];
    int root(int u) { return par[u] < 0 ? u : par[u] = root(par[u]); }
    bool Union(int u, int v) {
        if ((u = root(u)) == (v = root(v))) return false;
        if (par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return true;
    }

    int solve(int ar, int ac, int br, int bc) {
        int cnt(0);
        for (int i = 1; i <= mp.size(); ++i)
            par[i] = ar <= a[i].ff && a[i].ff <= br && ac <= a[i].ss && a[i].ss <= bc ? (++cnt, -1) : 0;

        // inside or outside
        if (cnt == 0) {
            for (pii p : arr_set) {
                if (ar <= p.ff && p.ff <= br && ac <= p.ss && p.ss <= bc) return 1;
            }
            return 0;
        }

        for (int i = 1; i <= mp.size(); ++i) if (par[i]) {
            for (int k = 0; k < 4; ++k) {
                pii p = a[i];
                p.ff += dr[k];
                p.ss += dc[k];
                if (mp.count(p)) {
                    int j = mp[p];
                    if (par[j]) cnt -= Union(i, j);
                }
            }
        }
        return cnt;
    }
}

void init(int R, int C, int SR, int SC, int M, char *S) {
    num['E'] = 0, num['W'] = 1, num['S'] = 2, num['N'] = 3;
    r = R, c = C, sr = SR, sc = SC, m = M;
    for (int i = 0; i < m; ++i) s.push_back(S[i]);
    if (r <= 50 && c <= 50)
        subtask1::init();
    else if (r == 2)
        subtask2::init();
    else
        subtask3::init();
}

int colour(int ar, int ac, int br, int bc) {
    if (r <= 50 && c <= 50)
        return subtask1::solve(ar, ac, br, bc);
    else if (r == 2)
        return subtask2::solve(ar, ac, br, bc);
    else
        return subtask3::solve(ar, ac, br, bc);
}

/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message

rainbow.cpp: In function 'void subtask1::init()':
rainbow.cpp:24:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |             sr += dr[num[c]];
      |                          ^
rainbow.cpp:25:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   25 |             sc += dc[num[c]];
      |                          ^
rainbow.cpp: In function 'void subtask2::init()':
rainbow.cpp:58:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |             sr += dr[num[c]];
      |                          ^
rainbow.cpp:59:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |             sc += dc[num[c]];
      |                          ^
rainbow.cpp: In function 'void subtask3::init()':
rainbow.cpp:85:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   85 |             sr += dr[num[c]];
      |                          ^
rainbow.cpp:86:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |             sc += dc[num[c]];
      |                          ^
rainbow.cpp: In function 'int subtask3::solve(int, int, int, int)':
rainbow.cpp:112:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<std::pair<int, int>, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for (int i = 1; i <= mp.size(); ++i)
      |                         ~~^~~~~~~~~~~~
rainbow.cpp:123:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<std::pair<int, int>, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for (int i = 1; i <= mp.size(); ++i) if (par[i]) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 11 ms 452 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 51 ms 3592 KB Output is correct
4 Correct 57 ms 3804 KB Output is correct
5 Correct 54 ms 3736 KB Output is correct
6 Correct 56 ms 3812 KB Output is correct
7 Correct 53 ms 3688 KB Output is correct
8 Correct 52 ms 3680 KB Output is correct
9 Correct 51 ms 3828 KB Output is correct
10 Correct 54 ms 3852 KB Output is correct
11 Correct 52 ms 3704 KB Output is correct
12 Correct 51 ms 3740 KB Output is correct
13 Correct 50 ms 3900 KB Output is correct
14 Correct 48 ms 3788 KB Output is correct
15 Correct 55 ms 3672 KB Output is correct
16 Correct 53 ms 3704 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 291 ms 34172 KB Output is correct
3 Correct 216 ms 34284 KB Output is correct
4 Correct 294 ms 34136 KB Output is correct
5 Correct 162 ms 25732 KB Output is correct
6 Incorrect 32 ms 3936 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 11 ms 452 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3065 ms 16856 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 11 ms 452 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3065 ms 16856 KB Time limit exceeded
19 Halted 0 ms 0 KB -