oj.uz

답안 #678413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678413 2023-01-05T19:14:16 Z jhwest2 바이러스 (JOI19_virus) C++14
100 / 100
 585 ms 127956 KB 
#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int N = 707070;
const int INF = 1e9 + 10;

int n, m, len, a[N], limit[1 << 4]; string s;

int encode(char c) {
    if (c == 'S')
        return 0;
    else if (c == 'E')
        return 1;
    else if (c == 'N')
        return 2;
    else
        return 3;
}
int f(int x, int y) { 
    return m * (x - 1) + (y - 1) + 1;
}
pair<int, int> g(int x) {
    return { (x - 1) / m + 1, (x - 1) % m + 1 };
}
bool in(int x, int y) {
    return (1 <= x && x <= n && 1 <= y && y <= m);
}

int par[N], anc[N], vis[N];
vector<int> cell[N], adj[N];
bool bad[N];

int Find(int a) {
    return par[a] = (par[a] == a) ? a : Find(par[a]);
}
bool ok(int v, int r) { // check if cell v is reachable from component r
    auto [x, y] = g(v);
    if (!in(x, y) || a[v] == 0 || Find(v) == r)
        return false;
    
    int msk = 0;
    for (int t = 0; t < 4; t++) {
        int nx = x + dx[t];
        int ny = y + dy[t];
        int w = f(nx, ny);

        if (in(nx, ny) && a[w] && Find(w) == r)
            msk |= 1 << t;
    }
    return a[v] <= limit[msk];
}
void Union(int a, int b) {
    a = Find(a); b = Find(b);
    if (a != b) {
        if (cell[a].size() < cell[b].size()) {
            swap(a, b);
            anc[a] = anc[b];
        }
        par[b] = a;

        for (int v : cell[b]) {
            cell[a].push_back(v);

            auto [x, y] = g(v);
            for (int t = 0; t < 4; t++) {
                int nx = x + dx[t];
                int ny = y + dy[t];
                int w = f(nx, ny);

                if (in(nx, ny) && ok(w, a))
                    adj[a].push_back(w);
            }
        }
        vector<int>().swap(cell[b]);
        vector<int>().swap(adj[b]);
    }
}
bool dfs(int v) {
    auto [x, y] = g(v); 
    for (int t = 0; t < 4; t++) {
        int nx = x + dx[t];
        int ny = y + dy[t];
        int w = f(nx, ny);

        if (in(nx, ny) && ok(w, v))
            adj[v].push_back(w);
    }
    int s = Find(v);
    while (!adj[s].empty()) {
        int z = adj[s].back(); 
        adj[s].pop_back();

        if (!ok(z, s))
            continue;

        if (vis[z] == 0) {
            vis[z] = 1;
            anc[z] = s;
            bool f = dfs(z);

            if (!f) {
                vis[v] = 2;
                bad[s] = 1;
                return false;
            }
        }
        else if (vis[z] == 1) {
            while (Find(s) != Find(z)) {
                Union(anc[s], s);
                s = Find(s);
            }
        }
        else {
            vis[v] = 2;
            bad[s] = 1;
            return false;
        }
        s = Find(v);
    }
    vis[v] = 2;
    return true;
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> len >> n >> m >> s;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) 
            cin >> a[f(i, j)];
    
    // upper bound for each direction set
    s += s;
    for (int msk = 0; msk < (1 << 4); msk++) {
        int cnt = 0, maxv = 0;
        for (int i = 0; i < 2 * len; i++) {
            if (msk >> encode(s[i]) & 1)
                ++cnt;
            else {
                maxv = max(maxv, cnt);
                cnt = 0;
            }
        }
        maxv = max(maxv, cnt);
        
        if (cnt == 2 * len)
            limit[msk] = INF;
        else
            limit[msk] = maxv;
    }
    
    for (int i = 1; i <= n * m; i++) {
        par[i] = i;
        cell[i].push_back(i);
    }
    for (int i = 1; i <= n * m; i++) {
        if (a[i] && !vis[i]) {
            vis[i] = 1;
            dfs(i);
        }
    }

    for (int i = 1; i <= n * m; i++) 
        if (a[i] && Find(i) == i)
            bad[anc[i]] = 1;

    map<int, int> mp;
    for (int i = 1; i <= n * m; i++) 
        if (a[i] && Find(i) == i && !bad[i])
            mp[cell[i].size()] += cell[i].size();
    
    cout << mp.begin()->first << '\n';
    cout << mp.begin()->second << '\n';
}

Compilation message

virus.cpp: In function 'bool ok(int, int)':
virus.cpp:39:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     auto [x, y] = g(v);
      |          ^
virus.cpp: In function 'void Union(int, int)':
virus.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |             auto [x, y] = g(v);
      |                  ^
virus.cpp: In function 'bool dfs(int)':
virus.cpp:81:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     auto [x, y] = g(v);
      |          ^

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 33748 KB Output is correct
2 Correct 286 ms 74532 KB Output is correct
3 Correct 257 ms 84288 KB Output is correct
4 Correct 241 ms 81612 KB Output is correct
5 Correct 202 ms 61648 KB Output is correct
6 Correct 17 ms 33492 KB Output is correct
7 Correct 415 ms 63852 KB Output is correct
8 Correct 99 ms 44640 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 33556 KB Output is correct
2 Correct 20 ms 33880 KB Output is correct
3 Correct 37 ms 33948 KB Output is correct
4 Correct 20 ms 33956 KB Output is correct
5 Correct 39 ms 33876 KB Output is correct
6 Correct 38 ms 34148 KB Output is correct
7 Correct 16 ms 33552 KB Output is correct
8 Correct 36 ms 33876 KB Output is correct
9 Correct 18 ms 33616 KB Output is correct
10 Correct 19 ms 33932 KB Output is correct
11 Correct 17 ms 33672 KB Output is correct
12 Correct 18 ms 33876 KB Output is correct
13 Correct 34 ms 33912 KB Output is correct
14 Correct 33 ms 33932 KB Output is correct
15 Correct 35 ms 34136 KB Output is correct
16 Correct 39 ms 33892 KB Output is correct
17 Correct 27 ms 33748 KB Output is correct
18 Correct 18 ms 33708 KB Output is correct
19 Correct 38 ms 33932 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 33748 KB Output is correct
2 Correct 286 ms 74532 KB Output is correct
3 Correct 257 ms 84288 KB Output is correct
4 Correct 241 ms 81612 KB Output is correct
5 Correct 202 ms 61648 KB Output is correct
6 Correct 17 ms 33492 KB Output is correct
7 Correct 415 ms 63852 KB Output is correct
8 Correct 99 ms 44640 KB Output is correct
9 Correct 17 ms 33556 KB Output is correct
10 Correct 20 ms 33880 KB Output is correct
11 Correct 37 ms 33948 KB Output is correct
12 Correct 20 ms 33956 KB Output is correct
13 Correct 39 ms 33876 KB Output is correct
14 Correct 38 ms 34148 KB Output is correct
15 Correct 16 ms 33552 KB Output is correct
16 Correct 36 ms 33876 KB Output is correct
17 Correct 18 ms 33616 KB Output is correct
18 Correct 19 ms 33932 KB Output is correct
19 Correct 17 ms 33672 KB Output is correct
20 Correct 18 ms 33876 KB Output is correct
21 Correct 34 ms 33912 KB Output is correct
22 Correct 33 ms 33932 KB Output is correct
23 Correct 35 ms 34136 KB Output is correct
24 Correct 39 ms 33892 KB Output is correct
25 Correct 27 ms 33748 KB Output is correct
26 Correct 18 ms 33708 KB Output is correct
27 Correct 38 ms 33932 KB Output is correct
28 Correct 570 ms 124456 KB Output is correct
29 Correct 307 ms 81948 KB Output is correct
30 Correct 398 ms 127060 KB Output is correct
31 Correct 447 ms 63564 KB Output is correct
32 Correct 449 ms 64104 KB Output is correct
33 Correct 248 ms 77440 KB Output is correct
34 Correct 585 ms 127844 KB Output is correct
35 Correct 411 ms 103244 KB Output is correct
36 Correct 520 ms 67672 KB Output is correct
37 Correct 505 ms 89248 KB Output is correct
38 Correct 531 ms 127956 KB Output is correct
39 Correct 342 ms 76812 KB Output is correct
40 Correct 392 ms 71672 KB Output is correct
41 Correct 233 ms 78280 KB Output is correct
42 Correct 419 ms 106164 KB Output is correct
43 Correct 313 ms 83696 KB Output is correct
44 Correct 104 ms 44700 KB Output is correct