Submission #800501

#	Time	Username	Problem	Language	Result	Execution time	Memory
800501		thimote75	Virus Experiment (JOI19_virus)	C++14	0 / 100	2068 ms	262144 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 (set<int> &interieur, 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 = interieur.find(S) != interieur.end();
    bool hN = interieur.find(N) != interieur.end();
    bool hW = interieur.find(W) != interieur.end();
    bool hE = interieur.find(E) != interieur.end();

    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 MFC {
    set<int> frontiere;
    set<int> routes;
    set<int> interieur;

    set<int> rem_routes;

    MFC () = default;

    int getRoute () {
        while (routes.size() != 0) {
            int route = (*routes.begin());
            routes.erase(route);

            if (interieur.find(route) != interieur.end()) continue ;
            rem_routes.insert(route);

            return route;
        }

        return -1;
    }
    int roadCount () {
        int res = 0;
        for (int u : routes)
            if (interieur.find(u) == interieur.end())
                res ++;
        for (int u : rem_routes)
            if (interieur.find(u) == interieur.end())
                res ++;
        
        return res;
    }

    void merge (MFC* other) {
        if (other->frontiere.size() > frontiere.size())
            other->frontiere.swap(frontiere);
        if (other->interieur.size() > interieur.size())
            other->interieur.swap(interieur);
        if (other->routes.size() > routes.size())
            other->routes.swap(routes);
        if (other->rem_routes.size() > rem_routes.size())
            other->rem_routes.swap(rem_routes);
        
        for (int u : other->interieur)
            interieur.insert(u);
        for (int u : other->routes)
            routes.insert(u);
        for (int u : other->rem_routes)
            rem_routes.insert(u);
        for (int u : other->frontiere) {
            if (check_road(interieur, u)) {
                if (frontiere.find(u) != frontiere.end())
                    frontiere.erase(u);
                
                routes.insert(u);
            } else frontiere.insert(u);
        }
    }
};

struct UFD {
    vector<MFC*> metadatas;
    idata parents;

    UFD () = default;
    UFD (int size) {
        metadatas.resize(size);
        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);

        parents[b] = a;
        metadatas[a]->merge(metadatas[b]);
    }
};

UFD ufd;

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;
}

bdata visited, visiting;
idata depth;

int dfs (int node, int parent, int _depth) {
    if (visiting[node]) {
        return _depth - depth[node] - 1;
    }
    if (visited[node]) return 0;

    visited [node] = true;
    visiting[node] = true;
    depth   [node] = _depth;

    MFC* mfc = ufd.metadatas[ufd.boss(node)];
    while (true) {
        int data = mfc->getRoute();
        if (data == -1) break ;

        data = ufd.boss(data);

        int res = dfs(data, node, _depth + 1);
        if (res == 0) continue ;

        ufd.merge(parent, node);
        return res - 1;
    }

    return 0;
}

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);
    }

    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);

    for (int i = 0; i < R * C; i ++) {
        MFC* mfc = new MFC();
        ufd.metadatas[i] = mfc;
        if (U[i] == 0) continue ;

        mfc->interieur.insert(i);

        vector<int> adjacent;
        if (i >= C) adjacent.push_back(i - C);
        if (i < R * C - C) adjacent.push_back(i + C);
        if (i % C != 0) adjacent.push_back(i - 1);
        if (i % C != C - 1) adjacent.push_back(i + 1);

        set<int> G; G.insert(i);

        for (int adj : adjacent) {
            if (check_road(G, adj)) mfc->routes.insert(adj);
            else mfc->frontiere.insert(adj);
        }
    }

    visited.resize(R * C);
    visiting.resize(R * C);
    depth.resize(R * C);

    for (int i = 0; i < R * C; i ++) {
        if (visited[i]) continue ;
    
        dfs(i, -1, 0);
    }
    
    int res = 1e9;
    int cnt = 0;
    for (int u = 0; u < R * C; u ++) {
        int v = ufd.boss(u);
        if (u != v) continue ;

        int rsize = ufd.metadatas[v]->roadCount();
        if (rsize != 0) continue ;

        int size = ufd.metadatas[v]->interieur.size();
        if (size == 0) continue ;
        if (size > res) continue ;
        if (size != res) cnt = 0;

        cnt += size; res = size;
    }

    cout << res << endl << cnt << endl;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80