oj.uz

Submission #545820

# Submission time Handle Problem Language Result Execution time Memory
545820 2022-04-05T14:00:30 Z Monarchuwu Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 1577 ms 391228 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;
    map<pii, int> mp;
    pii a[N << 3];
    void init() {
        vis.emplace(sr, sc);
        for (char c : s) {
            sr += dr[num[c]];
            sc += dc[num[c]];
            vis.emplace(sr, sc);
        }

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

    int par[N << 3];
    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 = 0; 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 = 0; i < mp.size(); ++i) if (par[i]) {
            pii p = a[i];
            for (int k = 0; k < 8; ++k) {
                p.ff += dr[k];
                p.ss += dc[k];
                if (ar <= p.ff && p.ff <= br && ac <= p.ss && p.ss <= bc)
                    cnt -= Union(i, mp[p]);
            }
        }
        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:114: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]
  114 |         for (int i = 0; i < mp.size(); ++i)
      |                         ~~^~~~~~~~~~~
rainbow.cpp:117: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]
  117 |         for (int i = 0; i < mp.size(); ++i) if (par[i]) {
      |                         ~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 5 ms 368 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 424 KB Output is correct
12 Correct 8 ms 404 KB Output is correct
13 Correct 6 ms 392 KB Output is correct
14 Correct 4 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 340 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 340 KB Output is correct
3 Correct 65 ms 3532 KB Output is correct
4 Correct 66 ms 3788 KB Output is correct
5 Correct 72 ms 3892 KB Output is correct
6 Correct 66 ms 3764 KB Output is correct
7 Correct 67 ms 3676 KB Output is correct
8 Correct 59 ms 3584 KB Output is correct
9 Correct 79 ms 3772 KB Output is correct
10 Correct 67 ms 3832 KB Output is correct
11 Correct 83 ms 3736 KB Output is correct
12 Correct 48 ms 3712 KB Output is correct
13 Correct 51 ms 3808 KB Output is correct
14 Correct 51 ms 3776 KB Output is correct
15 Correct 52 ms 3656 KB Output is correct
16 Correct 50 ms 3696 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 Runtime error 1512 ms 391228 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 5 ms 368 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 424 KB Output is correct
12 Correct 8 ms 404 KB Output is correct
13 Correct 6 ms 392 KB Output is correct
14 Correct 4 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 340 KB Output is correct
18 Runtime error 1577 ms 386688 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 11 ms 340 KB Output is correct
5 Correct 5 ms 368 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 8 ms 424 KB Output is correct
12 Correct 8 ms 404 KB Output is correct
13 Correct 6 ms 392 KB Output is correct
14 Correct 4 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 340 KB Output is correct
18 Runtime error 1577 ms 386688 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -