oj.uz

답안 #545829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545829 2022-04-05T14:13:47 Z Monarchuwu 무지개나라 (APIO17_rainbow) C++17
23 / 100
 3000 ms 34352 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)) {
                    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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 11 ms 464 KB Output is correct
4 Correct 10 ms 468 KB Output is correct
5 Correct 4 ms 392 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 9 ms 340 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 6 ms 464 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 324 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 55 ms 3816 KB Output is correct
4 Correct 58 ms 4096 KB Output is correct
5 Correct 56 ms 4056 KB Output is correct
6 Correct 65 ms 3932 KB Output is correct
7 Correct 71 ms 3968 KB Output is correct
8 Correct 55 ms 3916 KB Output is correct
9 Correct 53 ms 4056 KB Output is correct
10 Correct 54 ms 4144 KB Output is correct
11 Correct 70 ms 3916 KB Output is correct
12 Correct 50 ms 4016 KB Output is correct
13 Correct 52 ms 4048 KB Output is correct
14 Correct 52 ms 4008 KB Output is correct
15 Correct 52 ms 4036 KB Output is correct
16 Correct 53 ms 3896 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 324 ms 34268 KB Output is correct
3 Correct 270 ms 34352 KB Output is correct
4 Correct 391 ms 34316 KB Output is correct
5 Correct 187 ms 25792 KB Output is correct
6 Incorrect 39 ms 4012 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 11 ms 464 KB Output is correct
4 Correct 10 ms 468 KB Output is correct
5 Correct 4 ms 392 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 9 ms 340 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 6 ms 464 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Execution timed out 3055 ms 16716 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 11 ms 464 KB Output is correct
4 Correct 10 ms 468 KB Output is correct
5 Correct 4 ms 392 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 9 ms 340 KB Output is correct
12 Correct 8 ms 340 KB Output is correct
13 Correct 6 ms 464 KB Output is correct
14 Correct 5 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Execution timed out 3055 ms 16716 KB Time limit exceeded
19 Halted 0 ms 0 KB -