oj.uz

Submission #387526

# Submission time Handle Problem Language Result Execution time Memory
387526 2021-04-08T18:28:09 Z mohamedsobhi777 Virus Experiment (JOI19_virus) C++14
6 / 100
 2000 ms 5484 KB 
#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

const int N = 800 + 7;
const ll mod = 1e9 + 7;

int n, m, k, Min, Cnt;
int a[N][N], b[N][N];
int mov[100000 + 8];
string st;
int col;
int viz[N][N];
int m1[4] = {1, -1, 0, 0}, m2[4] = {0, 0, 1, -1};
int mask[16] ;

bool chk(int A, int B)
{
       int msk = 0 ; 
       for (int j = 0 ;j < 4; ++ j){
              int nx = A + m1[j] ; 
              int ny = B + m2[j] ; 
              if(nx >= 0 &&nx < n && ny >= 0 && ny < m && viz[nx][ny] == col){
                     msk|=(1<<j) ; 
              }
       }
       return mask[msk] >= a[A][B] || mask[msk] >= k ;
}

int get(vi arr){
       int best = 0;
       int sum = 0;
       for (int i = 0; i < k; ++i)
       {
              if (!arr[i])
                     break;
              best++;
       }
       for (int i = k - 1; ~i; --i)
       {
              if (!arr[i])
                     break;
              best++;
       }

       for (int i = 0; i < k; ++i)
       {
              if (!arr[i])
              {
                     best = max(best, sum);
                     sum = 0;
              }
              else
                     ++sum;
       }
       best = max(best, sum);
       return best; 
}

int solve(int x, int y)
{
       ++col;
       queue<pii> qu;
       qu.push({x, y});
       int ret = 1;

       viz[x][y] = col;

       while (sz(qu))
       {
              int A = qu.front().f;
              int B = qu.front().s;
              qu.pop();

              for (int j = 0; j < 4; ++j)
              {
                     int nx = A + m1[j];
                     int ny = B + m2[j];
                     if (nx >= 0 && nx < n && ny >= 0 && ny < m)
                     {
                            if (viz[nx][ny] != col && a[nx][ny] != 0 && chk(nx, ny))
                            {
                                   qu.push({nx, ny});
                                   ++ret;
                                   viz[nx][ny] = col;
                            }
                     }
              }
       }
       return ret;
}

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> k >> n >> m;
       cin >> st;
       for (int i = 0; i < k; ++i)
       {
              if (st[i] == 'S')
                     mov[i] = 0;
              else if (st[i] == 'N')
                     mov[i] = 1;
              else if (st[i] == 'W')
                     mov[i] = 3;
              else
                     mov[i] = 2;
       }

       for(int i = 0 ;i < (1<<4) ;++ i){
              vi arr(k,0) ; 
              for(int j= 0 ;j < k ;++ j){
                     arr[j] = (i&(1<<mov[j])) ; 
              }
              mask[i] = get(arr) ; 
       }

       for (int i = 0; i < n; ++i)
       {
              for (int j = 0; j < m; ++j)
              {
                     cin >> a[i][j];
              }
       }

       Min = 1e9;
       for (int i = 0; i < n; ++i)
       {
              for (int j = 0; j < m; ++j)
              {
                     if (!a[i][j])
                            continue;
                     int an = solve(i, j);
                     if (an < Min)
                     {
                            Min = an, Cnt = 1;
                     }
                     else if (an == Min)
                            ++Cnt;
              }
       }
       if(Min == 1e9)Min = 0 ;
       cout << Min << "\n";
       cout << Cnt << "\n";
       return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1136 KB Output is correct
2 Correct 204 ms 5484 KB Output is correct
3 Execution timed out 2086 ms 3316 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 11 ms 1788 KB Output is correct
3 Correct 16 ms 1788 KB Output is correct
4 Correct 11 ms 1788 KB Output is correct
5 Correct 15 ms 1788 KB Output is correct
6 Correct 271 ms 1788 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 15 ms 1788 KB Output is correct
9 Correct 172 ms 704 KB Output is correct
10 Correct 15 ms 1884 KB Output is correct
11 Correct 7 ms 620 KB Output is correct
12 Correct 445 ms 620 KB Output is correct
13 Correct 142 ms 1900 KB Output is correct
14 Correct 132 ms 1900 KB Output is correct
15 Correct 136 ms 1900 KB Output is correct
16 Correct 122 ms 1900 KB Output is correct
17 Correct 10 ms 1260 KB Output is correct
18 Correct 16 ms 748 KB Output is correct
19 Correct 16 ms 1904 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1136 KB Output is correct
2 Correct 204 ms 5484 KB Output is correct
3 Execution timed out 2086 ms 3316 KB Time limit exceeded
4 Halted 0 ms 0 KB -