oj.uz

답안 #477463

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477463 2021-10-02T08:48:41 Z FireGhost1301 Dango Maker (JOI18_dango_maker) C++11
33 / 100
 318 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int N = 3e3 + 1;
int n, m, cnt;

vector<vector<char>> c;
vector<vector<vector<int>>> id;
vector<vector<int>> g;
vector<int> deg;
vector<bool> vst;

inline bool check(char x, char y, char z) {
    return (x == 'R' && y == 'G' && z == 'W');
}

void solve() {
    cin >> n >> m;
    c.resize(n + 1, vector<char> (m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            cin >> c[i][j];
    }
    id.resize(n + 1, vector<vector<int>> (m + 1, vector<int> (2, 0)));
    for (int i = 1; i + 2 <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (check(c[i][j], c[i + 1][j], c[i + 2][j]))
                id[i][j][0] = ++cnt;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j + 2 <= m; ++j) {
            if (check(c[i][j], c[i][j + 1], c[i][j + 2]))
                id[i][j][1] = ++cnt;
        }
    }
    g.resize(cnt + 1);
    deg.resize(cnt + 1, 0);
    vst.resize(cnt + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (!id[i][j][1]) continue;
            if (id[i][j][0]) {
                g[id[i][j][0]].pb(id[i][j][1]);
                g[id[i][j][1]].pb(id[i][j][0]);
                ++deg[id[i][j][0]], ++deg[id[i][j][1]];
            }
            if (i - 1 > 0) {
                if (id[i - 1][j + 1][0]) {
                    g[id[i - 1][j + 1][0]].pb(id[i][j][1]);
                    g[id[i][j][1]].pb(id[i - 1][j + 1][0]);
                    ++deg[id[i - 1][j + 1][0]], ++deg[id[i][j][1]];
                }
            }
            if (i - 2 > 0) {
                if (id[i - 2][j + 2][0]) {
                    g[id[i - 2][j + 2][0]].pb(id[i][j][1]);
                    g[id[i][j][1]].pb(id[i - 2][j + 2][0]);
                    ++deg[id[i - 2][j + 2][0]], ++deg[id[i][j][1]];
                }
            }
        }
    }
    int ans = 0;
    set<pii> st;
    for (int i = 1; i <= cnt; ++i) {
        if (!deg[i]) {
            ++ans;
            continue;
        }
        st.insert(mp(deg[i], i));
    }
    while (!st.empty()) {
        ++ans;
        auto it = st.begin();
        pii x = *it;
        int u = x.se;
        st.erase(it);
        vst[u] = true;
        for (int v: g[u]) {
            if (vst[v]) continue;
            st.erase(st.find(mp(deg[v], v)));
            vst[v] = true;
            for (int q: g[v]) {
                if (!vst[q]) {
                    st.erase(st.find(mp(deg[q], q)));
                    --deg[q];
                    st.insert(mp(deg[q], q));
                }
            }
        }
    }
    cout << ans;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 0 ms 204 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Correct 0 ms 204 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 0 ms 204 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 0 ms 204 KB Output is correct
44 Correct 0 ms 204 KB Output is correct
45 Correct 0 ms 204 KB Output is correct
46 Correct 0 ms 204 KB Output is correct
47 Correct 0 ms 204 KB Output is correct
48 Correct 0 ms 204 KB Output is correct
49 Correct 0 ms 204 KB Output is correct
50 Correct 1 ms 204 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 0 ms 204 KB Output is correct
53 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 0 ms 204 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Correct 0 ms 204 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 0 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 0 ms 204 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 0 ms 204 KB Output is correct
43 Correct 0 ms 204 KB Output is correct
44 Correct 0 ms 204 KB Output is correct
45 Correct 0 ms 204 KB Output is correct
46 Correct 0 ms 204 KB Output is correct
47 Correct 0 ms 204 KB Output is correct
48 Correct 0 ms 204 KB Output is correct
49 Correct 0 ms 204 KB Output is correct
50 Correct 1 ms 204 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 0 ms 204 KB Output is correct
53 Correct 0 ms 204 KB Output is correct
54 Correct 1 ms 716 KB Output is correct
55 Correct 1 ms 844 KB Output is correct
56 Correct 3 ms 1484 KB Output is correct
57 Correct 3 ms 1644 KB Output is correct
58 Correct 116 ms 60484 KB Output is correct
59 Runtime error 318 ms 262148 KB Execution killed with signal 9
60 Halted 0 ms 0 KB -