Submission #795661

#	Time	Username	Problem	Language	Result	Execution time	Memory
795661		someone	Virus Experiment (JOI19_virus)	C++14	6 / 100	2089 ms	97972 KiB

virus

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

struct Candidat {
    pair<int, int> act, pre;
};

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

bool inComp[M][M];

bool cantInf[M][M];
set<pair<int, int>> cfc[M][M];
pair<int, int> acces[M][M], same[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) {
    return inComp[adj.x][adj.y];
    //act = getCFC(act), adj = getCFC(adj);
    //return cfc[act.x][act.y].find(adj) != cfc[act.x][act.y].end();
}

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

bool check(pair<int, int> coo) {
    for(int i = 0; i < 4; i++) {
        int x = coo.x + dl[i], y = coo.y + dc[i];
        if(valid(x, y) && hasAcces(x, y, coo.x, coo.y))
            return true;
    }
    return false;
}

void solve() {
    vector<Candidat> candidat;
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++) {
            if(check({i, j})) {
                candidat.push_back({{i, j}, {i, j}});
            } else {
                cantInf[i][j] = true;
                //cout << "CAN'T " << i << ' ' << j << '\n';
            }
        }
    while(!candidat.empty()) {
        auto cand = candidat.back();
        candidat.pop_back();

        bool nouv = false;
        //cout << "CANDIDAT " << cand.act.x << ' ' << cand.act.y << '\n';
        //for(pair<int, int> coo : cfc[cand.pre.x][cand.pre.y]) {
        for(pair<int, int> coo : cfc[cand.act.x][cand.act.y]) {
            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(cantInf[x][y]) {
                            nouv = false;
                            cfc[cand.act.x][cand.act.y].insert({x, y});
                        } else if(getAcces({x, y}) != cand.act) {
                            //suppr candidat
                            //cout << "      SUPPR\n";
                            acces[cand.act.x][cand.act.y] = getCFC({x, y});
                        } else {
                            //merge de CFC
                            //cout << "      MERGE\n";
                            auto act = cand.act, 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]);
                            for(pair<int, int> cas : cfc[pre.x][pre.y])
                                cfc[act.x][act.y].insert(cas);
                            same[pre.x][pre.y] = act;
                            acces[pre.x][pre.y] = act;
                            candidat.push_back({act, pre});
                        }
                    }
                }
            }
            if(nouv) break;
        }
        //cout << '\n';
        if(!nouv) {
            //CFC minimale
            int sz = (int)cfc[cand.act.x][cand.act.y].size(), cnt = 0;
            for(pair<int, int> pii : cfc[cand.act.x][cand.act.y])
                if(!cantInf[pii.x][pii.y])
                    cnt++;
            if(mini == sz) nb += cnt;
            else if(mini > sz && sz != 1) {
                nb = cnt;
                mini = sz;
            }
        }
    }
}

void reset() {
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            inComp[i][j] = false;
}

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].insert({i, j});
            same[i][j] = acces[i][j] = {i, j};
        }

    //solve();
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) if(u[i][j] != INF) {
            reset();
            int cnt = 0;
            vector<pair<int, int>> v;
            v.push_back({i, j});
            while(!v.empty()) {
                auto coo = v.back();
                v.pop_back();
                if(!inComp[coo.x][coo.y]) {
                    cnt++;
                    inComp[coo.x][coo.y] = true;
                    for(int k = 0; k < 4; k++) {
                        int x = coo.x + dl[k], y = coo.y + dc[k];
                        if(valid(x, y) && !inComp[x][y] && hasAcces(x, y, coo.x, coo.y)) {
                            v.push_back({x, y});
                        }
                    }
                }
            }
            if(cnt < mini) {
                mini = cnt;
                nb = 1;
            } else if(mini == cnt) {
                nb++;
            }
        }
    }
    cout << mini << '\n' << nb << '\n';
}

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