QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#283598#1127. Virus ExperimentMax_s_xaM14 83ms18016kbC++145.2kb2023-12-14 21:30:442023-12-14 21:30:44

Judging History

This is the latest submission verdict.

  • [2023-12-14 21:30:44]
  • Judged
  • Verdict: 14
  • Time: 83ms
  • Memory: 18016kb
  • [2023-12-14 21:30:44]
  • Submitted

answer

#include <iostream>
#include <algorithm>
#include <queue>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXR = 810, MAXN = 64e4 + 10, MAXM = 1e5 + 10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int M, n, m, rs[MAXR][MAXR];
char dir[MAXM << 1];

inline int Tr(char ch) {return (ch == 'N' ? 0 : ch == 'E' ? 1 : ch == 'S' ? 2 : 3);}
int mxlen[18];
inline int C(int i, int j) {return (i - 1) * m + j;}
inline pair <int, int> C(int x) {return make_pair((x + m - 1) / m, (x - 1) % m + 1);}

int fa[MAXN];
int Find(int k) {return k == fa[k] ? k : fa[k] = Find(fa[k]);}
inline void Union(int u, int v)
{
    u = Find(u), v = Find(v);
    if (u != v) fa[u] = v;
}

int cnd[MAXN], top, mch[MAXN];
int vis[MAXN], idx;
queue < pair <int, int> > q;
inline bool Check(int x, int y)
{
    if (x < 1 || x > n || y < 1 || y > m) return 0;
    int s = 0;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
        // cout << xx << " " << yy << " " << vis[C(xx, yy)] << "\n";
        if (vis[C(xx, yy)] == idx) s ^= (1 << i);
    }
    // cout << "Check " << x << " " << y << " " << s << " " << idx << "\n";
    return mxlen[s] >= rs[x][y];
}
inline pair <int, int> BFS(int st)
{
    auto cur = C(st); int x = cur.first, y = cur.second;
    int cop = Find(st), sz = 0;
    if (rs[x][y] == 2e9) return make_pair(-1, 2e9);
    while (!q.empty()) q.pop();
    q.push(cur), idx++;
    while (!q.empty())
    {
        cur = q.front(), x = cur.first, y = cur.second, q.pop();
        // cout << x << " " << y << " " << idx << "\n";
        vis[C(x, y)] = idx, sz++;
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (vis[C(xx, yy)] == idx) continue;
            if (!Check(xx, yy)) continue;
            if (Find(C(xx, yy)) != cop) return make_pair(C(xx, yy), 0);
            q.push(make_pair(xx, yy));
        }
    }
    return make_pair(-1, sz);
}

int main()
{
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(M), Read(n), Read(m);
    Read(dir + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            Read(rs[i][j]);
            if (!rs[i][j]) rs[i][j] = 2e9;
        }
    for (int i = 1; i <= M; i++) dir[i + M] = dir[i];
    for (int s = 1; s < 16; s++)
    {
        int cnt = 0;
        for (int i = 1; i <= 2 * M; i++)
            if (s & (1 << Tr(dir[i]))) cnt++, mxlen[s] = max(mxlen[s], cnt);
            else cnt = 0;
        if (mxlen[s] == 2 * M) mxlen[s] = 1e9;
    }
    for (int i = 1; i <= n * m; i++) fa[i] = i;
    while (1)
    {
        top = 0;
        for (int i = 1; i <= n * m; i++)
            if (fa[i] == i) cnd[++top] = i;
        for (int i = 1; i <= top; i++) mch[cnd[i]] = BFS(cnd[i]).first;//, cout << cnd[i] << " " << mch[cnd[i]] << "\n";
        bool flag = 0;
        for (int i = 1; i <= top; i++)
            if (~mch[cnd[i]]) Union(cnd[i], mch[cnd[i]]), flag = 1;
        if (!flag) break;
    }
    int mn = 1e9, ans = 0;
    for (int i = 1; i <= n * m; i++)
        if (fa[i] == i)
        {
            auto cur = BFS(i);
            if (cur.second < mn) mn = ans = cur.second;
            else if (cur.second == mn) ans += cur.second;
        }
    Write(mn, '\n'), Write(ans, '\n');
    return 0;
}

詳細信息

Subtask #1:

score: 14
Accepted

Test #1:

score: 14
Accepted
time: 0ms
memory: 15900kb

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 58ms
memory: 17800kb

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: 28ms
memory: 17340kb

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: 28ms
memory: 17592kb

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: 0
Accepted
time: 83ms
memory: 17740kb

input:

9999 800 800
WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...

output:

1
639810

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 13856kb

input:

10 800 1
EWEWWWWWWW
1
1
1
0
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
1
1
0
1
1
0
0
1
1
0
1
0
1
0
0
0
0
1
1
1
1
1
0
0
1
1
0
1
0
0
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
1
1
0
1
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
1
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
1
1
0
0
1
1
0
0
1
1
1
1
1
1
1
0
...

output:

1
392

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 65ms
memory: 18016kb

input:

100000 800 800
WWEEWEEWEEEWEEWWWWWEEEWWWEEEWEWWEWEEEWWWEEEWEWWWWEEWWEWEEEEEEWWEEEWWWWWWWEWWWEEWWWWWWEEWEWEWEEWEWEWEWWEEEEWEEEEWEWWWWEEEEWWWEWWWEWWEWEWWWEWEWEWWEEEEEEWEEEEEWEEEEEWEEEWEEEEEEEWEWWWEWWWEWWWWEEWWEWEEEWWWWEEEEEEWWWEEEEEWEWEWWEWEEEEEEEWEEWWEWWEEWWEEEEEWWEWEWEEWWEEWEEWEWWWWEEWEWEWEEEEEEEWEW...

output:

800
640000

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 45ms
memory: 16848kb

input:

100000 500 500
EWWWEWEWEEWWEEEEEWWEWEEWEWWEEWEEEWEWWWWEWEWWWEWWEWEEWWWWWWWEEEEEEEEEWEEEEEEWEWWEEEEEEEWWEEEWWWEEWWEWEEWWEWWWWWWWWEWEEEWEWWWEWEWWEEEEEEEWWEEEWWWEEWWEEEWEWEWEWWWEWWWEEEWEEWWWWEWWEWWEWWEEEEWWEEWEEEEWEEWWEEEEWWWEWWWEWEWWEWWWEWEEEEEWWWEWEWEEEWWWEEEWEWWWEEWEWEEEWWWWEWEEWWEEWEEEWEWEWWEWEWWWE...

output:

1
227098

result:

ok 2 lines

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 6
Accepted
time: 0ms
memory: 13800kb

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
33

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 14132kb

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: -6
Wrong Answer
time: 15ms
memory: 13860kb

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:

151
151

result:

wrong answer 1st lines differ - expected: '27', found: '151'

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%