oj.uz

Submission #800630

# Submission time Handle Problem Language Result Execution time Memory
800630 2023-08-01T17:07:45 Z thimote75 Virus Experiment (JOI19_virus) C++14
100 / 100
 1321 ms 210560 KB 
#include <bits/stdc++.h>

using namespace std;

using bdata = vector<bool>;

using idata = vector<int>;
using igrid = vector<idata>;
using ispac = vector<igrid>;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

int R, C;

const int MASK_S = 1;
const int MASK_N = 2;
const int MASK_W = 4;
const int MASK_E = 8;

idata U;
int max_buffer[16];
bool check_road (idata &visited, int stage, int u) {
    if (U[u] == 0) return false;

    int S = u + C;
    int N = u - C;
    int W = u % C == 0     ? - 1 : u - 1;
    int E = u % C == C - 1 ? - 1 : u + 1;

    bool hS = S >= 0 && S < R * C ? visited[S] == stage : false;
    bool hN = N >= 0 && N < R * C ? visited[N] == stage : false;
    bool hW = W >= 0 && W < R * C ? visited[W] == stage : false;
    bool hE = E >= 0 && E < R * C ? visited[E] == stage : false;

    for (int m = 1; m < 16; m ++) {
        if (U [u] > max_buffer[m]) continue ;

        if ((m & MASK_S) != 0 && (!hS)) continue ;
        if ((m & MASK_N) != 0 && (!hN)) continue ;
        if ((m & MASK_W) != 0 && (!hW)) continue ;
        if ((m & MASK_E) != 0 && (!hE)) continue ;

        return true;
    }

    return false;
}

struct Mare {
    set<int> cases;
    int center;

    bool is_in (int x) {
        return cases.find(x) != cases.end();   
    }
    void merge (Mare *other) {
        if (cases.size() < other->cases.size()) cases.swap(other->cases);

        for (int u : other->cases) cases.insert(u);
    }
    bool operator< (const Mare &right) const {
        if (cases.size() == right.cases.size()) return center < right.center;
        return cases.size() < right.cases.size();
    }
    bool operator== (const Mare &right) const {
        return center == right.center;
    }
};

using vMare = vector<Mare*>;
using sMare = set<Mare*>;

struct UFD {
    vMare mares;
    sMare sorted_mares;
    idata parents;

    int rem () {
        return sorted_mares.size();
    }
    Mare* pop () {
        Mare* mare = *sorted_mares.begin();
        sorted_mares.erase(mare);

        return mare;
    }

    UFD () = default;
    UFD (int size) {
        mares.resize(size);
        for (int i = 0; i < size; i ++) {
            mares[i] = new Mare();
            mares[i]->cases.insert(i);
            mares[i]->center = i;

            sorted_mares.insert(mares[i]);
        }

        parents.resize(size);
        iota(parents.begin(), parents.end(), 0);
    }

    int boss (int x) {
        if (parents[x] != x)
            parents[x] = boss(parents[x]);
        return parents[x];
    }
    void merge (int a, int b) {
        a = boss(a); b = boss(b);
        if (a == b) return ;

        parents[b] = a;

        sorted_mares.erase(mares[a]);
        sorted_mares.erase(mares[b]);

        mares[a]->merge(mares[b]);
        sorted_mares.insert(mares[a]);
    }
};

int solve_buffer (bdata &values) {
    int r = 0;
    int l = 0;
    int c = 0;

    for (bool u : values) {
        if (u) {
            if (l == 0) { l = 1; c = 0; }

            c ++;
            r = max(r, c);
        } else l = 0;
    }
    for (bool u : values) {
        if (u) {
            if (l == 0) { l = 1; c = 0; }

            c ++;
            r = max(r, c);
        } else l = 0;
    }

    return r;
}

UFD ufd;

idata visited;
int stage = 0;
pair<int, int> find_outside (Mare *mare) {
    if (U[mare->center] == 0) return { -1, 1e9 };
    int start = mare->center;
    stage ++;
    
    queue<int> q;
    visited[start] = stage;
    q.push(start);

    int cnt = 0;

    while (q.size() != 0) {
        int curr = q.front(); q.pop();
        //dbg(curr);

        cnt ++;

        for (int adjacent : { 
                curr - C, 
                curr + C, 
                curr % C == 0 ? - 1 : curr - 1, 
                curr % C == C + 1 ? - 1 : curr + 1
            }) {
            if (adjacent < 0 || adjacent >= R * C) continue ;
            //dbg(adjacent);
            //dbg(visited[adjacent]);
            //dbg(stage);
            //dbg((int) (visited[adjacent] == stage));

            if (visited[adjacent] == stage) continue ;

            //dbg((int) (check_road(visited, stage, adjacent)));
            if (!check_road(visited, stage, adjacent)) continue ;

            //dbg((int) (mare.is_in(adjacent)));
            if (!mare->is_in(adjacent)) return { adjacent, cnt };
            q.push(adjacent);
            visited[adjacent] = stage;
        }
    }

    return { -1, cnt };
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T; cin >> T;
    cin >> R >> C;

    string buffer;
    cin >> buffer;

    bdata values(T);
    for (int m = 1; m < 16; m ++) {
        for (int i = 0; i < T; i ++) {
            values[i] = false;

            if (buffer[i] == 'S' && (0 != (m & MASK_S))) values[i] = true;
            if (buffer[i] == 'N' && (0 != (m & MASK_N))) values[i] = true;
            if (buffer[i] == 'W' && (0 != (m & MASK_W))) values[i] = true;
            if (buffer[i] == 'E' && (0 != (m & MASK_E))) values[i] = true;
        }

        max_buffer[m] = solve_buffer(values);
        if (max_buffer[m] > T) max_buffer[m] = 1e9;
    }

    U.resize(R * C);

    for (int r = 0; r < R; r ++) {
        for (int c = 0; c < C; c ++) {
            cin >> U[r * C + c];
        }
    }

    ufd = UFD(R * C);
    visited.resize(R * C);

    while (ufd.rem() != 0) {
        Mare* mare = ufd.pop();

        int out = find_outside(mare).first;
        if (out == -1) continue ;

        ufd.sorted_mares.insert(ufd.mares[mare->center]);
        ufd.merge(out, mare->center);
    }

    int res = 1e9;
    int cnt = 0;
    for (int u = 0; u < R * C; u ++) {
        if (ufd.boss(u) != u) continue ;

        int size = find_outside(ufd.mares[u]).second;
        if (size > res) continue ;
        if (size < res) cnt = 0;

        res  = size;
        cnt += size;
    }

    cout << res << "\n" << cnt << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 537 ms 113048 KB Output is correct
3 Correct 546 ms 113044 KB Output is correct
4 Correct 664 ms 114184 KB Output is correct
5 Correct 427 ms 116760 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 777 ms 114528 KB Output is correct
8 Correct 188 ms 45920 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 468 KB Output is correct
3 Correct 23 ms 468 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 23 ms 468 KB Output is correct
6 Correct 25 ms 916 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 23 ms 472 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 8 ms 468 KB Output is correct
11 Correct 2 ms 764 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 23 ms 916 KB Output is correct
14 Correct 22 ms 852 KB Output is correct
15 Correct 23 ms 920 KB Output is correct
16 Correct 23 ms 784 KB Output is correct
17 Correct 14 ms 724 KB Output is correct
18 Correct 4 ms 852 KB Output is correct
19 Correct 24 ms 844 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 537 ms 113048 KB Output is correct
3 Correct 546 ms 113044 KB Output is correct
4 Correct 664 ms 114184 KB Output is correct
5 Correct 427 ms 116760 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 777 ms 114528 KB Output is correct
8 Correct 188 ms 45920 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 7 ms 468 KB Output is correct
11 Correct 23 ms 468 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 23 ms 468 KB Output is correct
14 Correct 25 ms 916 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 23 ms 472 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 8 ms 468 KB Output is correct
19 Correct 2 ms 764 KB Output is correct
20 Correct 3 ms 980 KB Output is correct
21 Correct 23 ms 916 KB Output is correct
22 Correct 22 ms 852 KB Output is correct
23 Correct 23 ms 920 KB Output is correct
24 Correct 23 ms 784 KB Output is correct
25 Correct 14 ms 724 KB Output is correct
26 Correct 4 ms 852 KB Output is correct
27 Correct 24 ms 844 KB Output is correct
28 Correct 1147 ms 144496 KB Output is correct
29 Correct 670 ms 127428 KB Output is correct
30 Correct 1006 ms 192660 KB Output is correct
31 Correct 758 ms 149056 KB Output is correct
32 Correct 741 ms 153712 KB Output is correct
33 Correct 639 ms 114368 KB Output is correct
34 Correct 1321 ms 210560 KB Output is correct
35 Correct 936 ms 152792 KB Output is correct
36 Correct 1156 ms 161484 KB Output is correct
37 Correct 1189 ms 208332 KB Output is correct
38 Correct 1137 ms 167596 KB Output is correct
39 Correct 745 ms 115380 KB Output is correct
40 Correct 749 ms 116452 KB Output is correct
41 Correct 556 ms 114380 KB Output is correct
42 Correct 948 ms 163232 KB Output is correct
43 Correct 893 ms 180712 KB Output is correct
44 Correct 174 ms 45896 KB Output is correct