Submission #795712

#	Time	Username	Problem	Language	Result	Execution time	Memory
795712		someone	Virus Experiment (JOI19_virus)	C++14	100 / 100	401 ms	195916 KiB

virus

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;

const int N = 2e5 + 42, M = 805, INF = 1e18 + 42;

int dl[] = {-1, 0, 1, 0},
    dc[] = {0, -1, 0, 1};
char ch[N], w[] = {'N', 'W', 'S', 'E'};

pair<int, int> acces[M][M], same[M][M];
vector<pair<int, int>> cfc[M][M], toAdd[M][M];
int m, row, col, mini = INF, nb = 0, maxi[16], u[M][M];

pair<int, int> getCFC(pair<int, int> coo) {
    if(same[coo.x][coo.y] == coo)
        return coo;
    return same[coo.x][coo.y] = getCFC(same[coo.x][coo.y]);
}

pair<int, int> getAcces(pair<int, int> coo) {
    if(acces[coo.x][coo.y] == coo)
        return coo;
    return acces[coo.x][coo.y] = getAcces(acces[coo.x][coo.y]);
}

inline bool valid(int x, int y) {
    return -1 < x && x < row && -1 < y && y < col;
}

inline bool sameCFC(pair<int, int> act, pair<int, int> adj) {
    act = getCFC(act), adj = getCFC(adj);
    return act == adj;
}

inline bool hasAcces(int l, int c, int x, int y) {
    int mask = 0;
    for(int i = 0; i < 4; i++) {
        int adjX = l + dl[i], adjY = c + dc[i];
        if(valid(adjX, adjY) && sameCFC({x, y}, {adjX, adjY}))
            mask += (1 << i);
    }
    //cout << "      " << u[l][c] << ' ' << maxi[mask] << ' ' << mask << '\n';
    return u[l][c] <= maxi[mask];
}

void solve() {
    vector<pair<int, int>> candidat;
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            if(u[i][j] != INF)
                candidat.push_back({i, j});
    while(!candidat.empty()) {
        pair<int, int> cand = candidat.back();
        candidat.pop_back();

        bool nouv = false;
        //cout << "CANDIDAT " << cand.x << ' ' << cand.y << '\n';
        //for(pair<int, int> coo : cfc[cand.pre.x][cand.pre.y]) {
        while(!toAdd[cand.x][cand.y].empty()) {
            pair<int, int> coo = toAdd[cand.x][cand.y].back();
            toAdd[cand.x][cand.y].pop_back();
            if(valid(coo.x, coo.y)) {
                //cout << "  TEST " << coo.x << ' ' << coo.y << '\n';
                for(int i = 0; i < 4 && !nouv; i++) {
                    int x = coo.x + dl[i], y = coo.y + dc[i];
                    //cout << "    CHECKING " << x << ' ' << y << '\n';
                    if(valid(x, y) && !sameCFC(coo, {x, y}) && hasAcces(x, y, coo.x, coo.y)) {
                        nouv = true;
                        //cout << "      NEW\n";
                        if(getAcces({x, y}) != cand) {
                            //suppr candidat
                            //cout << "      SUPPR\n";
                            acces[cand.x][cand.y] = getCFC({x, y});
                        } else {
                            //merge de CFC
                            //cout << "      MERGE\n";
                            auto act = cand, pre = getCFC({x, y});
                            if(cfc[act.x][act.y].size() < cfc[pre.x][pre.y].size()) {
                                swap(cfc[pre.x][pre.y], cfc[pre.x][pre.y]);
                                swap(toAdd[pre.x][pre.y], toAdd[pre.x][pre.y]);
                            }
                            for(pair<int, int> cas : cfc[pre.x][pre.y]) {
                                cfc[act.x][act.y].push_back(cas);
                                toAdd[act.x][act.y].push_back(cas);
                            }
                            toAdd[act.x][act.y].push_back(coo);
                            same[pre.x][pre.y] = act;
                            acces[pre.x][pre.y] = act;
                            candidat.push_back(act);
                        }
                    }
                }
            }
            if(nouv) break;
        }
        //cout << '\n';
        if(!nouv) {
            //CFC minimale
            int sz = (int)cfc[cand.x][cand.y].size();
            if(mini == sz) nb += sz;
            else if(mini > sz) mini = nb = sz;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> m >> row >> col;
    for(int i = 0; i < m; i++)
        cin >> ch[i];
    for(int i = 0; i < m; i++)
        ch[i + m] = ch[i];
    for(int i = 0; i < 16; i++) {
        int len = 0;
        for(int j = 0; j < 2*m; j++) {
            int wind = 0;
            for(int k = 0; k < 4; k++)
                if(w[k] == ch[j] && (i & (1 << k)))
                    wind = 1;
            if(wind == 0)
                len = 0;
            else
                len++;
            maxi[i] = max(maxi[i], len);
        }
        if(maxi[i] == 2*m) maxi[i] = N;
    }

    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++) {
            cin >> u[i][j];
            if(u[i][j] == 0)
                u[i][j] = INF;
            cfc[i][j].push_back({i, j});
            toAdd[i][j].push_back({i, j});
            same[i][j] = acces[i][j] = {i, j};
        }

    solve();
    cout << mini << '\n' << nb << '\n';
}

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