oj.uz

Submission #677702

# Submission time Handle Problem Language Result Execution time Memory
677702 2023-01-04T07:54:37 Z benedict0724 Virus Experiment (JOI19_virus) C++17
6 / 100
 2000 ms 5948 KB 
#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long ll;

int dir[200002], bit[16];
bool visited[802][802];
int pos[802][802], U[802][802];
int M, R, C;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int cnt = 0;

void init()
{
    cnt = 0;
    for(int i=1;i<=R;i++) for(int j=1;j<=C;j++)
    {
        pos[i][j] = 0;
        visited[i][j] = false;
    }
}

void dfs(int x, int y)
{
    visited[x][y] = true;
    cnt++;
    for(int d=0;d<4;d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if(nx < 1 || nx > R || ny < 1 || ny > C || U[nx][ny] == 0 || visited[nx][ny]) continue;
        pos[nx][ny] += (1<<d);
        if(U[nx][ny] <= bit[pos[nx][ny]]) dfs(nx, ny);
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> M >> R >> C;
    string D; cin >> D;
    for(int i=0;i<16;i++)
    {
        for(int j=0;j<2*M;j++) dir[j] = 0;
        for(int j=0;j<M;j++)
        {
            if(D[j] == 'N' && (i & 1)) dir[j] = dir[j+M] = 1;
            if(D[j] == 'S' && (i & 2)) dir[j] = dir[j+M] = 1;
            if(D[j] == 'W' && (i & 4)) dir[j] = dir[j+M] = 1;
            if(D[j] == 'E' && (i & 8)) dir[j] = dir[j+M] = 1;
        }
        int now = 0;
        bit[i] = 0;
        for(int j=0;j<2*M;j++)
        {
            if(dir[j] == 1) now++;
            else now = 0;
            bit[i] = max(bit[i], now);
        }
        if(now == 2 * M) bit[i] = 300000;
    }
    
    for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) cin >> U[i][j];
    int ans = R * C + 1;
    int ansN = 1;
    for(int i=1;i<=R;i++) for(int j=1;j<=C;j++)
    {
        if(U[i][j] == 0) continue;
        init();
        dfs(i, j);
        if(cnt == ans) ansN++;
        else if(cnt < ans)
        {
            ans = cnt;
            ansN = 1;
        }
    }
    cout << ans << "\n" << ansN << "\n";
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Execution timed out 2067 ms 5948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 1364 KB Output is correct
3 Correct 26 ms 1320 KB Output is correct
4 Correct 8 ms 1364 KB Output is correct
5 Correct 25 ms 1332 KB Output is correct
6 Correct 138 ms 1792 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 25 ms 1620 KB Output is correct
9 Correct 56 ms 668 KB Output is correct
10 Correct 6 ms 1364 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 176 ms 732 KB Output is correct
13 Correct 77 ms 1808 KB Output is correct
14 Correct 87 ms 1696 KB Output is correct
15 Correct 76 ms 1776 KB Output is correct
16 Correct 91 ms 1680 KB Output is correct
17 Correct 16 ms 1236 KB Output is correct
18 Correct 8 ms 596 KB Output is correct
19 Correct 28 ms 1688 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Execution timed out 2067 ms 5948 KB Time limit exceeded
3 Halted 0 ms 0 KB -