QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#287126#1127. Virus Experimentwhdywjd0 68ms15084kbC++144.8kb2023-12-19 18:53:042023-12-19 18:53:05

Judging History

This is the latest submission verdict.

  • [2023-12-19 18:53:05]
  • Judged
  • Verdict: 0
  • Time: 68ms
  • Memory: 15084kb
  • [2023-12-19 18:53:04]
  • 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_M];
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;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 14
Accepted
time: 3ms
memory: 7220kb

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 52ms
memory: 14900kb

input:

10 800 800
WWWWEWWEWW
7 3 7 5 10 6 9 6 5 8 1 10 1 6 6 1 8 9 3 7 1 3 1 4 9 3 4 2 5 4 5 7 8 10 4 6 2 8 7 2 1 5 3 10 9 10 1 7 6 2 1 8 3 4 10 5 3 3 3 9 2 2 6 1 6 5 6 3 7 9 7 5 8 5 4 3 7 6 9 3 4 9 1 2 7 1 3 4 6 10 8 4 4 9 1 2 6 1 4 4 10 6 10 4 1 5 1 8 5 2 1 9 4 10 9 2 7 9 4 1 6 5 1 6 6 10 10 1 3 10 6 4 8...

output:

1
230450

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 34ms
memory: 14964kb

input:

10 800 800
WWWWWWWWWW
15314 11896 14475 25269 31478 32227 37443 24837 1353 32232 8163 3206 34713 17755 6870 20331 29572 19341 12557 36054 14768 990 30502 32464 15439 17070 15514 32216 37546 25514 27706 3028 26652 17247 13171 40866 36133 9550 22005 24048 33764 25331 12936 27462 27217 33096 19096 3919...

output:

1
800

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 17ms
memory: 14896kb

input:

31 800 800
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
800

result:

ok 2 lines

Test #5:

score: -14
Wrong Answer
time: 68ms
memory: 15084kb

input:

9999 800 800
WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...

output:

1
639818

result:

wrong answer 2nd lines differ - expected: '639810', found: '639818'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 2ms
memory: 7276kb

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%