Submission #800681

#	Time	Username	Problem	Language	Result	Execution time	Memory
800681		rnl42	Virus Experiment (JOI19_virus)	C++14	6 / 100	2078 ms	21200 KiB

virus

#include <bits/stdc++.h>
using namespace std;
#define amax(a, b) a = max(a, b)
#define cellid(r, c) (r*C+c)
#define extract(cell) (cell/C)][(cell%C)
    
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
    
    
constexpr int INF = 1e9+42;
    
int M, R, C;
vector<vector<int>> U;
    
string to_s(int cell) {
    return to_string(cell/C)+","+to_string(cell%C);
}
    
struct patate {
    int centre;
    int num_cases = 1;
    bool operator<(const patate& other) const {
        return num_cases > other.num_cases;
    }
};
    
struct Dir {
    int v, h;
    bool ok(int cell) {
        int r = cell/C, c = cell%C;
        if (0 <= r+v && r+v < R && 0 <= c+h && c+h < C && U[r+v][c+h]) {
            return true;
        } else {
            return false;
        }
    }
    int next(int cell) {
        return cell+h+v*C;
    }
};
    
const Dir DIRS[] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
int maxconsecutive[1<<4];
//vector<patate> patates;
vector<int> uf;
vector<int> numchilds;
priority_queue<patate> pq;
int timer = 1;
vector<int> vu;
vector<int> bestcost;
int ans = INF;
int ansq = 0;
//vector<int> maskvoisin;
    
int root(int u) {
    return uf[u] == u ? u : uf[u] = root(uf[u]);
}
    
void debug_plateau() {
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (U[r][c]) {
                auto color = root(cellid(r, c));
                color %= 14;
                if (color >= 7) color += 4;
                //cerr << "\033[" << color+31 << "m" << root(cellid(r, c)) << "\033[0m ";
            } else {
                //cerr << "\033[90m" << root(cellid(r, c)) << "\033[0m ";
            }
        }
        //cerr << "\n";
    }
    
}
    
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> M >> R >> C;
    string dirs;
    cin >> dirs;
    dirs.append(dirs);
    char _map[256];
    _map['S'] = 0;
    _map['W'] = 1;
    _map['N'] = 2;
    _map['E'] = 3;
    uf.resize(R*C);
    vu.resize(R*C);
    numchilds.assign(R*C, 1);
    bestcost.assign(R*C, INF);
    //maskvoisin.resize(R*C);
    iota(uf.begin(), uf.end(), 0);
    for (int mask = 0; mask < 1<<4; mask++) {
        int l = 0;
        for (char c : dirs) {
            if ((mask >> _map[(unsigned char)c]) & 1) l++;
            else l = 0;
            maxconsecutive[mask] = max(maxconsecutive[mask], l);
        }
        if (maxconsecutive[mask] >= M) maxconsecutive[mask] = INF;
        //cerr << "maxconsecutive[" << mask << "] = " << maxconsecutive[mask] << endl;
    }
    U.assign(R, vector<int>(C));
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            cin >> U[r][c];
            if (U[r][c]) {
                pq.push({cellid(r, c), 1});
            }
        }
    }
    
    /*for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            int cell = cellid(r, c);
            if (!U[r][c]) continue;
            queue<int> q;
            q.push(cell);
            timer++;
            vu[cell] = timer;
            int num_explore = 0;
            while (!q.empty()) {
                auto u = q.front(); q.pop();
                num_explore++;
    
                for (auto dir : DIRS) {
                    int next = dir.next(u);
                    if (dir.ok(u)) {
                        int i = 2;
                        int mask = 0;
                        for (auto dir2 : DIRS) {
                            int k = dir2.next(next);
                            if (dir2.ok(next) && vu[k] == vu[cell]) {
                                mask += 1<<i;
                            }
                            i++, i &= 3;
                        }
                        if (U[extract(next)] <= maxconsecutive[mask]) {
                            if (vu[next] != timer) {
                                vu[next] = timer;
                                q.push(next);
                            }
                        }
                    }
                }
            }
            if (num_explore == ans) {
                ansq++;
            } else if (num_explore < ans) {
                ans = num_explore;
                ansq = 1;
            }
        }
    }
    cout << ans << '\n' << ansq << '\n';
    
    
    return 0;*/
    
    
    debug_plateau();
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        if (root(cur.centre) != cur.centre || numchilds[cur.centre] != cur.num_cases) continue;
    
        //cerr << "\033[1m\033[93mBFS DEPUIS " << to_s(cur.centre) << "\033[0m" << endl;
        timer++;
        queue<int> q;
        q.push(cur.centre);
        vu[cur.centre] = timer;
        bool stopbfs = false;
        int num_explore = 0;
        vector<int> explored;
        while (!q.empty() && !stopbfs) {
            auto u = q.front(); q.pop();
            explored.push_back(u);
            num_explore++;
            for (auto dir : DIRS) {
                int next = dir.next(u);
                //cerr << "dir" << dir.v << ":" << dir.h << "   u=" << u << endl;
                if (dir.ok(u)) {
                    int i = 2;
                    int mask = 0;
                    for (auto dir2 : DIRS) {
                        int k = dir2.next(next);
                        if (dir2.ok(next) && vu[k] == vu[cur.centre]) {
                            mask += 1<<i;
                        }
                        i++, i &= 3;
                    }
                    //cerr << "vers dir" << dir.v << ":" << dir.h << "   mask=" << mask << endl;
                    if (U[extract(next)] <= maxconsecutive[mask]) {
                        //cerr << "arête valide vers dir" << dir.v << ":" << dir.h << endl;
                        // arête valide
                        if (vu[next] != timer && root(next) == cur.centre) {
                            vu[next] = timer;
                            q.push(next);
                            //cerr << "ajout à la file de " << next << "  a pour root" << root(next) << endl;
                        } else if (root(next) != cur.centre) {
                            //cerr << "FUSION " << to_s(root(cur.centre)) << " " << to_s(root(next)) << endl;
                            uf[cur.centre] = root(next);
                            numchilds[root(next)] += numchilds[cur.centre];
                            //cerr << "push " << to_s(root(next)) << " " << numchilds[root(cur.centre)] << endl;
                            pq.push({root(next), numchilds[root(next)]});
                            stopbfs = true;
                            break;
                        }
                    }
                }
            }
        }
        debug_plateau();
        if (!stopbfs) {
            /*if (num_explore == ans) {
                ansq += num_explore;
            } else if (num_explore < ans) {
                ans = num_explore;
                ansq = num_explore;
            }*/
            ans = min(ans, num_explore);
            for (auto k : explored) {
                bestcost[k] = min(bestcost[k], num_explore);
            }
            //cerr << "\033[1m\033[92mmise à jour du min " << num_explore << "\033[0m" << endl;
        }
        //cerr << "--------------\n\n\n" << endl;
    }
    //...
    for (int i = 0; i < R*C; i++) {
        if (bestcost[i] == ans) ansq++;
    }
    cout << ans << '\n' << ansq << '\n';
}

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