제출 #800637

#제출 시각아이디문제언어결과실행 시간메모리
800637Arturgo바이러스 (JOI19_virus)C++14
0 / 100
281 ms56448 KiB
#include <bits/stdc++.h> using namespace std; struct Point { int lig, 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]; // taille, couleurs 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(derPasse[cur.lig][cur.col] == curPasse) return {-1, -1}; if(resistances[cur.lig][cur.col] == 0) 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(!(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; } int n = 50; while(n--) { pair<int, Point> patate = *patates.begin(); Point cur = patate.second; curPasse++; Point nouv = dfs_set(cur, cur, true); if(nouv.lig == -1) { break; } patates.erase(patates.begin()); 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(pair<int, Point> patate : patates) { curPasse++; nbVus = 0; Point cur = patate.second; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...