Submission #800630

#	Time	Username	Problem	Language	Result	Execution time	Memory
800630		thimote75	Virus Experiment (JOI19_virus)	C++14	100 / 100	1321 ms	210560 KiB

virus

#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 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80