oj.uz

Submission #801818

# Submission time Handle Problem Language Result Execution time Memory
801818 2023-08-02T07:54:03 Z Arturgo Virus Experiment (JOI19_virus) C++14
100 / 100
 824 ms 104660 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8692 KB Output is correct
2 Correct 458 ms 59288 KB Output is correct
3 Correct 564 ms 61548 KB Output is correct
4 Correct 503 ms 59136 KB Output is correct
5 Correct 370 ms 61632 KB Output is correct
6 Correct 26 ms 14788 KB Output is correct
7 Correct 674 ms 59392 KB Output is correct
8 Correct 188 ms 30072 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8856 KB Output is correct
2 Correct 22 ms 9080 KB Output is correct
3 Correct 77 ms 9088 KB Output is correct
4 Correct 19 ms 9080 KB Output is correct
5 Correct 79 ms 9168 KB Output is correct
6 Correct 79 ms 9592 KB Output is correct
7 Correct 20 ms 8596 KB Output is correct
8 Correct 77 ms 9356 KB Output is correct
9 Correct 22 ms 9000 KB Output is correct
10 Correct 21 ms 9108 KB Output is correct
11 Correct 23 ms 9172 KB Output is correct
12 Correct 19 ms 9100 KB Output is correct
13 Correct 66 ms 9468 KB Output is correct
14 Correct 64 ms 9332 KB Output is correct
15 Correct 68 ms 9328 KB Output is correct
16 Correct 69 ms 9336 KB Output is correct
17 Correct 78 ms 9296 KB Output is correct
18 Correct 29 ms 9156 KB Output is correct
19 Correct 82 ms 9328 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8692 KB Output is correct
2 Correct 458 ms 59288 KB Output is correct
3 Correct 564 ms 61548 KB Output is correct
4 Correct 503 ms 59136 KB Output is correct
5 Correct 370 ms 61632 KB Output is correct
6 Correct 26 ms 14788 KB Output is correct
7 Correct 674 ms 59392 KB Output is correct
8 Correct 188 ms 30072 KB Output is correct
9 Correct 23 ms 8856 KB Output is correct
10 Correct 22 ms 9080 KB Output is correct
11 Correct 77 ms 9088 KB Output is correct
12 Correct 19 ms 9080 KB Output is correct
13 Correct 79 ms 9168 KB Output is correct
14 Correct 79 ms 9592 KB Output is correct
15 Correct 20 ms 8596 KB Output is correct
16 Correct 77 ms 9356 KB Output is correct
17 Correct 22 ms 9000 KB Output is correct
18 Correct 21 ms 9108 KB Output is correct
19 Correct 23 ms 9172 KB Output is correct
20 Correct 19 ms 9100 KB Output is correct
21 Correct 66 ms 9468 KB Output is correct
22 Correct 64 ms 9332 KB Output is correct
23 Correct 68 ms 9328 KB Output is correct
24 Correct 69 ms 9336 KB Output is correct
25 Correct 78 ms 9296 KB Output is correct
26 Correct 29 ms 9156 KB Output is correct
27 Correct 82 ms 9328 KB Output is correct
28 Correct 760 ms 104660 KB Output is correct
29 Correct 824 ms 95076 KB Output is correct
30 Correct 780 ms 75804 KB Output is correct
31 Correct 621 ms 56544 KB Output is correct
32 Correct 636 ms 57292 KB Output is correct
33 Correct 558 ms 59280 KB Output is correct
34 Correct 801 ms 66896 KB Output is correct
35 Correct 585 ms 62244 KB Output is correct
36 Correct 804 ms 58920 KB Output is correct
37 Correct 740 ms 67112 KB Output is correct
38 Correct 750 ms 90052 KB Output is correct
39 Correct 646 ms 59264 KB Output is correct
40 Correct 676 ms 59528 KB Output is correct
41 Correct 551 ms 55760 KB Output is correct
42 Correct 703 ms 62324 KB Output is correct
43 Correct 811 ms 62572 KB Output is correct
44 Correct 195 ms 30120 KB Output is correct