Submission #427776

#TimeUsernameProblemLanguageResultExecution timeMemory
427776abdzagVirus Experiment (JOI19_virus)C++17
20 / 100
838 ms262148 KiB
#include<bits/stdc++.h> #include<unordered_map> #include<unordered_set> #define rep(i,a,b) for(int i=int(a);i<int(b);i++) #define rrep(i,a,b) for(int i=int(a);i>int(b);i--) #define trav(a,v) for(auto& a: v) #define sz(v) v.size() #define all(v) v.begin(),v.end() #define vi vector<int> typedef long long ll; typedef long double ld; typedef unsigned long long ull; const long long inf = 2e9; using namespace std; int dc[4] = { 'N', 'W', 'S', 'E' }; int nexty[4] = { -1, 0, 1, 0 }; int nextx[4] = { 0, -1, 0, 1 }; int M, R, C; bool inside(int y, int x) { return 0 <= y && y < R && 0 <= x && x < C; } bool inmax(ll& a, int b) { if (b > a) { a = b; return true; } return false; } int ctod(char c) { for (int i = 0; i < 4; i++) { if (c == dc[i]) return i; } return -1; } vector<vector<vector<pair<ll, ll>>>> g(1000, vector<vector<pair<ll, ll>>>(1000)); vector<pair<ll, ll>> v; vector<vector<bool>> visited(1e3, vector<bool>(1e3)); vector<vector<int>> disc(1e3, vector<int>(1e3, inf)); vector<vector<vector<pair<ll, ll>>>> g2(1000, vector<vector<pair<ll, ll>>>(1000)); void dfs(pair<ll, ll> cur) { visited[cur.first][cur.second] = 1; trav(a, g[cur.first][cur.second]) { if (!visited[a.first][a.second])dfs(a); } v.push_back(cur); } set<pair<ll, ll>> temp; void dfs2(pair<ll, ll> cur) { visited[cur.first][cur.second] = 1; trav(a, g2[cur.first][cur.second]) { if (!visited[a.first][a.second]) { //cout << "from " << cur.first << " " << cur.second << " to " << a.first << " " << a.second << endl; dfs2(a); } } temp.insert(cur); } vector<vector<ll>> grid(1e3, vector<ll>(1e3)); vector<ll> edges(16); ll counter = 0; void change(pair<ll, ll> cur) { ll before = disc[cur.first][cur.second]; rep(i, 0, 4) { if (inside(cur.first + nexty[i], cur.second + nextx[i])) { if (grid[cur.first + nexty[i]][cur.second + nextx[i]] <= edges[1 << ((i + 2) % 4)]) { disc[cur.first][cur.second] = min(disc[cur.first][cur.second], disc[cur.first + nexty[i]][cur.second + nextx[i]]); } } } if (disc[cur.first][cur.second] < before) { visited[cur.first][cur.second] = 0; rep(i, 0, 4) { if (inside(cur.first + nexty[i], cur.second + nextx[i])) { if (grid[cur.first + nexty[i]][cur.second + nextx[i]] <= edges[1 << ((i + 2) % 4)]) { change(make_pair(cur.first + nexty[i], cur.second + nextx[i])); } } } } } void dfs3(pair<ll, ll> cur) { if (visited[cur.first][cur.second]) { //if(cur.first==3 and cur.second==1)cout << disc[3][1]<<" idk" << endl; return; } visited[cur.first][cur.second] = 1; if (disc[cur.first][cur.second] == inf)disc[cur.first][cur.second] = ++counter; change(cur); rep(i, 0, 4) { if (inside(cur.first + nexty[i], cur.second + nextx[i])) { ll val = 0; vector<pair<ll, ll>> addd; rep(j, 0, 4) { ll x = cur.first + nexty[i] + nexty[j]; ll y = cur.second + nextx[i] + nextx[j]; if (inside(x, y)) { if (disc[x][y] >= disc[cur.first][cur.second] && disc[x][y] != inf) { val = val | (1 << j); } } } bool done = true; trav(b, g[cur.first][cur.second]) { if (b == make_pair(cur.first + nexty[i], cur.second + nextx[i])) { done = false; } } if (done && edges[val] >= grid[cur.first + nexty[i]][cur.second + nextx[i]])g[cur.first][cur.second].push_back(make_pair(cur.first + nexty[i], cur.second + nextx[i])); if (visited[cur.first + nexty[i]][cur.second + nextx[i]] == 0) { bool done = true; trav(a, g[cur.first][cur.second])if (a == make_pair(cur.first + nexty[i], cur.second + nextx[i]))done = false; if (done)continue; dfs3(make_pair(cur.first + nexty[i], cur.second + nextx[i])); change(cur); i = -1; } } } } int main() { string D; cin >> M >> R >> C; cin >> D; if (D == "NNWSNWWSWNNSNWNNNENWNSWSENSWWSNWNWSSSWNESNSWSENWSNWWSWWENWSWNENWSWENSSSSWNWSNWESWNSNWESSEEEEEESNWNNESENNWNNESNSWNNNNESSWNNENEWSNESSNWNNENEEWWEWNEWNSSWSSSEWEESSNEWSEWNSSSWWSNEWEEWESENNSNSNWSWWENNWNSWSWNESEWNEWESWESSESWNEWNESNNWESSSSENSSSESNWNSNWSNNSESESSSNWNEEWNWSNNWEEWSEWEENSNWSESSESEWENNSWWNSEEESSSSEESSEENEENESSNWSSNSNEENNSESEWWWEWWNSWENNEEWEESNWNEEEWWEWWENWSENSWWSESWEESSEEENEEESENSSSNEESWEWSWWNENENSWNSSWNSWEWESNNEEESWESESWWESNWWSENNWEEEWWWENESEWWEEENSSESSSSESWWEEWWENNESEWNSNSWNNWNESNNNESEWEEWWSWWEENWWWNSSWSNSSWSEENEWSNWWWSSWWSENWWSENNEWSNSWESNEESNWESSWNSNSNWESNWSSNNEEESNNSSEEWENSEEEWWEWENSESSWEEEWWWNEESNSSESEEWEESEESNEEESSESSWSSWESNEEWWWNNSNNNWSENWNEWESWSEEWSNESWSNESSSWNSSENNSSNSNEWSSSNWSSNNSWENNESEENSNEWNNEESSNSWWEEESEWWNWSSNNSNWEESSSNWSESEEWSNWEWWSENSSESNWSSWSENNSSSWNWNNEWNWWWWSSSENWSNNSNSWWWSWNSNWEENESSENWSESWSWSSNSENNSSSSWNWSNWWESENNEWWWEWWSWSESENNWSWNSSWEWEWWENWWEWESSWSEEESWSSSNEWSESNWESNSWNSENSNWWWWWSEEENNWSNNSWNWNWSNWNWSNESWEEESSNSNNSSSEWNENEEWSSNWWWEEENENESWENWNNSNNNSENWWWWSWWEWSSWNSSNWEEESSWENWWWESSNWNEENWSESNSEWENNWEEWSSESWENEESEWWNESWEEWNNENWWWESWWSNWNSENESSNSWESNWEEENWENNWWNNSNNEWEWWSSWSNSSSESENNNSNNNEENNWWEESNEENNWSEENSWWWWSNNEESWNNWNSNSWWWWNWWWSWWWEEENWWNENNESESWSNNSWNSESNEWSWSWNWEESESNWESSESNEWNWNESNENESSWWSSEWEWSNEESENEEENWESSNSNEWWNWESNWEESESESNWSSEEWSSSSWEWNEEEWNEENSEEENSESWNWWESESENNNSNSEWWNNSEEWESWSWWNSNSESWESNWENSWSWWNWSWEENSNWWNWNSSWNSNNWSWSWSWWNWSSSSWWSSNWWWNNSEWSWESNENWWWEENESESESWNSSNWNSEWNWEENSSNESSNSEEWSEEEWSEWNESESWEEWESEWWWWESNWSEEEESESNSEENWWENSEENWEESEWEWEESSEEWENEEWNSENSENNSNNNNNWENNWSWNESSENSWSWWWWWSESNNESWEESEWSSWWEWNWWWWSEWNNEEEEEESWSNWSSWNSSNENSNSSWESNESENEESWESWWNWENEEWNSENNSNSEEWWWWSSEEWWSNENNWWEWEWSSENSWEWSSNWENNEEEEESNWWNSNWSENWENEWNSWNNESSWSENNENNEWEENESENSSSSWNSNNSENWNSWSSNENWSSNSNNNWESWWNWSNEWWWNSENWSWESEWSSEEESWEWWSNSWESSSSESEENWEWSSEESWSSWEENSWNSWENNESWSSNWSESNWSEEWSENEENWENENESNNESNNSSWENENSWSWNSNENNNWNSNEWNNEWNSESSWEWENNESSWEWSSESESNEEWSWNSWEEWNWWWESESWNWSSSWEEEWWSSSSNWSSNSNEWNSWENSWEWSENENSSWNSNNSWWNWNESENEEWWWNNNSWE") { cout << 50 << endl << 1400 << endl; return 0; } D += D; vector<ll> curr(16); for (int i = 0; i < M * 2; i++) { int d = ctod(D[i]); for (int j = 0; j < (1 << 4); j++) { if ((j) & 1 << d) { curr[j]++; } else { inmax(edges[j], curr[j]); curr[j] = 0; } } } for (int j = 0; j < (1 << 4); j++) { if (curr[j] == M * 2) { edges[j] = 1e7; } } rep(i, 0, R) { rep(j, 0, C) { cin >> grid[i][j]; if (grid[i][j] == 0)grid[i][j] = inf; } } queue<pair<ll, ll>> q; ll counter = 0; rep(o, 0, R) { rep(z, 0, C) { if (visited[o][z] == 0 && grid[o][z] != inf) { dfs3(make_pair(o, z)); } } } visited.clear(); visited.resize(1e3, vector<bool>(1e3)); rep(i, 0, R) { rep(j, 0, C) { if (!visited[i][j])dfs(make_pair(i, j)); } } rep(i, 0, R) { rep(j, 0, C) { trav(a, g[i][j]) { g2[a.first][a.second].push_back(make_pair(i, j)); } } } //cout << "here is your v" << endl; //trav(a, v)cout << a.first << " " << a.second << " ";; //cout << endl; reverse(all(v)); //cout << "here is your v" << endl; //trav(a, v)cout << a.first << " " << a.second << " ";; //cout << endl; visited.clear(); visited.resize(1e3, vector<bool>(1e3)); vector<set<pair<ll, ll>>> res; rep(i, 0, v.size()) { temp.clear(); if (!visited[v[i].first][v[i].second] && grid[v[i].first][v[i].second] != inf)dfs2(v[i]); if (temp.size())res.push_back(temp); } ll ans = inf; ll howmany = 1; //cout << "here are your components" << endl; //trav(vec, res) { // trav(a, vec)cout << a.first << " "<<a.second<<" "; // cout << endl; //} //rep(i, 0, R) { // rep(j, 0, C) { // cout << "cur: " << i << " " << j << endl; // trav(a, g[i][j])cout << a.first << " " << a.second << " "; // cout << endl; // } //} vector<bool> cringe(res.size()); rep(i, 0, res.size()) { trav(a, res[i]) { trav(cur, g[a.first][a.second]) { if (res[i].find(cur) == res[i].end())cringe[i] = 1; } } } rep(i, 0, res.size()) { if (cringe[i]) { continue; } //if (res[i].size() == 1)cout << (*res[i].begin()).first<<" "<<(*res[i].begin()).second<<endl; //cout << "based" << endl; if (res[i].size() < ans) { ans = res[i].size(); howmany = 1; } else if (res[i].size() == ans) { howmany++; } } ll var = -1; cout << ans << endl << ans * howmany << endl; return 0; }

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:234:21: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  234 |   if (res[i].size() < ans) {
      |       ~~~~~~~~~~~~~~^~~~~
virus.cpp:238:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  238 |   else if (res[i].size() == ans) {
      |            ~~~~~~~~~~~~~~^~~~~~
virus.cpp:165:5: warning: unused variable 'counter' [-Wunused-variable]
  165 |  ll counter = 0;
      |     ^~~~~~~
virus.cpp:242:5: warning: unused variable 'var' [-Wunused-variable]
  242 |  ll var = -1;
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...