Submission #801818

#	Time	Username	Problem	Language	Result	Execution time	Memory
801818		Arturgo	Virus Experiment (JOI19_virus)	C++14	100 / 100	824 ms	104660 KiB

virus

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int lig, col;
    
    Point(int _lig = 0, int _col = 0) {
        lig = _lig;
        col = _col;
    }
};

Point operator + (const Point& a, const Point& b) {
    return {a.lig + b.lig, a.col + b.col};
}

bool operator < (const Point& a, const Point& b) {
    if(a.lig == b.lig)
        return a.col < b.col;
    return a.lig < b.lig;
}

bool operator == (const Point& a, const Point& b) {
    return a.lig == b.lig && a.col == b.col;
}

int nEtats, nLigs, nCols;
int resistances[1000][1000];
Point couleurs[1000][1000];
int tailles[1000][1000];

map<char, int> char_to_id = {
    {'S', 0},
    {'N', 1},
    {'E', 2},
    {'W', 3}
};

Point deps[4] = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};

int longest_segment[16];
set<pair<int, Point>> patates;

int curPasse = 0;
int nbVus = 0;
int derPasse[1000][1000];

Point dfs_set(Point cur, Point centre, bool actif = false) {
    if(cur.lig == 0 || cur.col == 0
    || cur.lig == nLigs + 1 || cur.col == nCols + 1) return {-1, -1};
    if(resistances[cur.lig][cur.col] == 0) return {-1, -1};
    
    if(derPasse[cur.lig][cur.col] == curPasse)
        return {-1, -1};
    
    bitset<4> mask;
    for(int iDep = 0;iDep < 4;iDep++) {
        Point v = cur + deps[iDep];
        mask[iDep] = (derPasse[v.lig][v.col] == curPasse);
    }
   
    if(longest_segment[mask.to_ulong()]
    >= resistances[cur.lig][cur.col] || actif) {
        derPasse[cur.lig][cur.col] = curPasse;
        nbVus++;
        
        if(!(couleurs[cur.lig][cur.col] == centre))
            return couleurs[cur.lig][cur.col];
        
        for(int iDep = 0;iDep < 4;iDep++) {
            Point ret = dfs_set(cur + deps[iDep], centre);
            if(ret.lig != -1) return ret;
        }
    }
   
    return {-1, -1};
}

void dfs_move(Point cur, Point from, Point to) {
    if(cur.lig == 0 || cur.col == 0
    || cur.lig == nLigs + 1 || cur.col == nCols + 1) return;
    if(resistances[cur.lig][cur.col] == 0) return;
    
    if(!(couleurs[cur.lig][cur.col] == from))
        return;
    
    couleurs[cur.lig][cur.col] = to;
    
    for(int iDep = 0;iDep < 4;iDep++) {
        dfs_move(cur + deps[iDep], from, to);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    
    cin >> nEtats >> nLigs >> nCols;
    
    string dirs;
    cin >> dirs;
    while(dirs.size() <= 200 * 1000)
        dirs = dirs + dirs;
    
    for(int iLig = 1;iLig <= nLigs;iLig++) {
        for(int iCol = 1;iCol <= nCols;iCol++) {
            cin >> resistances[iLig][iCol];
            
            if(resistances[iLig][iCol] != 0) {
                couleurs[iLig][iCol] = {iLig, iCol};
                tailles[iLig][iCol] = 1;
                
                patates.insert({1, {iLig, iCol}});
            }
        }
    }
    
    for(int iMask = 0;iMask < 16;iMask++) {
        bitset<4> bits(iMask);
        
        int opt_segment = 0, cur_segment = 0;
        for(char car : dirs) {
            if(bits[char_to_id[car]]) {
                cur_segment++;
                opt_segment = max(opt_segment, cur_segment);
            }
            else {
                cur_segment = 0;
            }
        }
        
        longest_segment[iMask] = opt_segment;
    }
    
    while(!patates.empty()) {
        pair<int, Point> patate = *patates.begin();
        
        Point cur = patate.second;
        
        curPasse++;
        Point nouv = dfs_set(cur, cur, true);
        
        patates.erase(*patates.begin());
        if(nouv.lig == -1) {
            continue;
        }
        
        dfs_move(cur, cur, nouv);
        patates.erase({tailles[nouv.lig][nouv.col], nouv});
        tailles[nouv.lig][nouv.col] += tailles[cur.lig][cur.col];
        patates.insert({tailles[nouv.lig][nouv.col], nouv});
    }
    
    int minVus = 1000 * 1000, nbSols = 0;
    
    for(int iLig = 1;iLig <= nLigs;iLig++) {
        for(int iCol = 1;iCol <= nCols;iCol++) {
            Point cur = {iLig, iCol};
            if(couleurs[iLig][iCol] == cur) {
                curPasse++;
                nbVus = 0;
                
                Point p = dfs_set(cur, cur, true);
                
                if(p.lig != -1) continue;
                
                if(nbVus < minVus) {
                    minVus = nbVus;
                    nbSols = 0;
                }
                if(nbVus == minVus) {
                    nbSols += nbVus;
                }
            }
        }
    }
    
    cout << minVus << endl << nbSols << endl;
    
    return 0;
}

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