oj.uz

Submission #545830

# Submission time Handle Problem Language Result Execution time Memory
545830 2022-04-05T14:15:34 Z Monarchuwu Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 34272 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;

        for (int i = 1; i <= mp.size(); ++i) if (par[i]) {
            for (int k = 0; k < 8; ++k) {
                pii p = a[i];
                p.ff += dr[k];
                p.ss += dc[k];
                if (mp.count(p) && ar <= p.ff && p.ff <= br && ac <= p.ss && p.ss <= bc) {
                    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:115: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]
  115 |         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 468 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 58 ms 3588 KB Output is correct
4 Correct 60 ms 3788 KB Output is correct
5 Correct 62 ms 3756 KB Output is correct
6 Correct 51 ms 3660 KB Output is correct
7 Correct 55 ms 3660 KB Output is correct
8 Correct 51 ms 3660 KB Output is correct
9 Correct 50 ms 3756 KB Output is correct
10 Correct 55 ms 3840 KB Output is correct
11 Correct 59 ms 3652 KB Output is correct
12 Correct 50 ms 3772 KB Output is correct
13 Correct 53 ms 3760 KB Output is correct
14 Correct 50 ms 3796 KB Output is correct
15 Correct 49 ms 3788 KB Output is correct
16 Correct 50 ms 3636 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 338 ms 34052 KB Output is correct
3 Correct 284 ms 34168 KB Output is correct
4 Correct 387 ms 34272 KB Output is correct
5 Correct 183 ms 25656 KB Output is correct
6 Incorrect 39 ms 3900 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 468 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3091 ms 16796 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 468 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3091 ms 16796 KB Time limit exceeded
19 Halted 0 ms 0 KB -