QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#287125#1127. Virus Experimentwhdywjd0 0ms11256kbC++144.8kb2023-12-19 18:51:552023-12-19 18:51:56

Judging History

This is the latest submission verdict.

  • [2023-12-19 18:51:56]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 11256kb
  • [2023-12-19 18:51:55]
  • Submitted

answer

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#define ll long long
#define _mp make_pair
#define _pb push_back
#define _1 first
#define _2 second
#define inf 2222222222222222222ll
#define MAX_N 1004
#define MAX_M 222222

using namespace std;

ll read(){ll x = 0;char c = 0, v = 0;do{c = getchar();if(c == '-')v = 1;} while(c < '0' || c > '9');do{x = (x << 3) + (x << 1) + c - '0';c = getchar();} while(c >= '0' && c <= '9');return v ? -x : x;}
char gtc(){char c = 0;while(c < 33)c = getchar();return c;}

template<size_t N>
struct vset
{
	int f[N];
	vset() { memset(f, 255, sizeof(f)); }
	int fath(int x) { return f[x] < 0 ? x : f[x] = fath(f[x]); }
	bool merge(int x, int p)
	{
		x = fath(x), p = fath(p);
		if(x == p)
			return 0;
		f[p] += f[x];
		f[x] = p;
		return 1;
	}
};

vset<MAX_N * MAX_N> st;

int k, n, m;
char s[MAX_N];
ll mxl[16]; // NESW

bool check(char s, int op) { return (s == 'N' && (op & 8)) || (s == 'E' && (op & 4)) || (s == 'S' && (op & 2)) || (s == 'W' && (op & 1)); }

ll f[MAX_N][MAX_N];

int pid(int i, int j) { return (i - 1) * m + j; }

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

int OUTID, SIZE;
bool ifc[MAX_N][MAX_N];
queue<pair<int, int> > q, emp;
vector<pair<int, int> > vec;

bool vis[MAX_N][MAX_N];

bool check(int x, int y)
{
    int sta = 0;
    for(int i = 0; i < 4; i++)
        if(ifc[x + dx[i]][y + dy[i]])
            sta |= (1 << i);
    return mxl[sta] >= f[x][y];
}

void clearr()
{
    q = emp;
    for(auto k: vec)
        ifc[k._1][k._2] = 0;
    vec.clear();
}

void bfsr(int x, int y)
{
    OUTID = SIZE = 0;
    q.push(_mp(x, y));
    vis[x][y] = ifc[x][y] = 1, vec._pb(_mp(x, y));
    while(!q.empty())
    {
        pair<int, int> k = q.front();
        q.pop();
        SIZE++;
        for(int i = 0; i < 4; i++)
        {
            int nx = k._1 + dx[i];
            int ny = k._2 + dy[i];
            if(!nx || nx == n + 1 || !ny || ny == m + 1 || !check(nx, ny))
                continue;
            if(st.fath(pid(x, y)) != st.fath(pid(nx, ny)))
            {
                OUTID = st.fath(pid(nx, ny));
                //printf("R\n");
                return;
            }
            if(vis[nx][ny])
                continue;
            /*if(x == 1 && y == 1)
                printf("%d %d %d %d\n", k._1, k._2, nx, ny);*/
            vis[nx][ny] = ifc[nx][ny] = 1, vec._pb(_mp(nx, ny)), q.push(_mp(nx, ny));
        }
    }
}

void bfs(int i, int j) { bfsr(i, j), clearr(); }

void MAIN()
{
    k = read();
    n = read();
    m = read();
    scanf("%s", s + 1);
    mxl[0] = 0, mxl[15] = inf;
    for(int op = 1; op <= 14; op++)
    {
        mxl[op] = 0;
        ll len = 0;
        for(int i = 1; i <= k; i++)
        {
            if(check(s[i], op))
                len++;
            else
                len = 0;
            mxl[op] = max(mxl[op], len);
        }
        for(int i = 1; i <= k; i++)
        {
            if(check(s[i], op))
                len++;
            else
                len = 0;
            mxl[op] = max(mxl[op], len);
        }
        if(mxl[op] >= k)
            mxl[op] = inf;
    }
    /*for(int i = 0; i < 16; i++)
        printf("%lld ", mxl[i]);
    printf("\n");*/
    for(int i = 0; i <= n + 1; i++)
        for(int j = 0; j <= m + 1; j++)
            if(!i || !j || i == n + 1 || j == m + 1)
                f[i][j] = inf + 2;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = read();
            if(!f[i][j])
                f[i][j] = inf + 2;
        }
    while(1)
    {
        bool flag = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                if(st.fath(pid(i, j)) == pid(i, j))
                {
                    bfs(i, j);
                    if(OUTID)
                        st.merge(pid(i, j), OUTID), flag = 1;
                }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                vis[i][j] = 0;
        if(!flag)
            break;
    }
    int mn = n * m, sum = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(st.fath(pid(i, j)) == pid(i, j))
            {
                bfs(i, j);
                //printf("%d %d %d\n", i, j, SIZE);
                if(SIZE < mn)
                    mn = sum = SIZE;
                else if(SIZE == mn)
                    sum += mn;
            }
    printf("%d\n%d\n", mn, sum);
}

void CLEAR()
{
    ;
}

void EXP()
{
    ;
}

int main()
{
    EXP();
    int T = 1;
    while(T--)
        MAIN(), CLEAR();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 11256kb

input:

10 10 10
NNNNSENESS
3 2 0 0 1 3 2 3 1 2
3 3 2 0 5 2 4 0 5 1
5 1 2 3 0 4 4 0 1 0
5 0 1 0 2 4 2 2 0 3
0 1 0 1 4 0 1 4 1 0
3 5 5 0 2 5 3 0 3 4
5 3 1 0 5 4 4 0 4 4
1 0 2 0 5 4 0 2 3 0
4 2 0 2 3 0 2 5 5 4
3 0 2 0 5 4 5 4 0 5

output:

1
38

result:

wrong answer 2nd lines differ - expected: '33', found: '38'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%