QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#283597 | #1127. Virus Experiment | Max_s_xaM | 14 | 60ms | 18128kb | C++14 | 5.2kb | 2023-12-14 21:23:44 | 2023-12-14 21:23:44 |
Judging History
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 (!Check(xx, yy)) continue;
if (Find(C(xx, yy)) != cop) return make_pair(C(xx, yy), 0);
if (vis[C(xx, yy)] != idx) 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;
int pre = 0;
while (1)
{
top = 0;
for (int i = 1; i <= n * m; i++)
if (fa[i] == i) cnd[++top] = i;
if (top == pre) break;
for (int i = 1; i <= top; i++) mch[cnd[i]] = BFS(cnd[i]).first;//, cout << cnd[i] << " " << mch[cnd[i]] << "\n";
for (int i = 1; i <= top; i++)
if (~mch[cnd[i]]) Union(cnd[i], mch[cnd[i]]);
pre = top;
}
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: 4ms
memory: 13700kb
input:
53768 10 50 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...
output:
1 10
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 48ms
memory: 18040kb
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: 9ms
memory: 17236kb
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: 19ms
memory: 17232kb
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: 60ms
memory: 17412kb
input:
9999 800 800 WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...
output:
1 639810
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 15856kb
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: 58ms
memory: 18128kb
input:
100000 800 800 WWEEWEEWEEEWEEWWWWWEEEWWWEEEWEWWEWEEEWWWEEEWEWWWWEEWWEWEEEEEEWWEEEWWWWWWWEWWWEEWWWWWWEEWEWEWEEWEWEWEWWEEEEWEEEEWEWWWWEEEEWWWEWWWEWWEWEWWWEWEWEWWEEEEEEWEEEEEWEEEEEWEEEWEEEEEEEWEWWWEWWWEWWWWEEWWEWEEEWWWWEEEEEEWWWEEEEEWEWEWWEWEEEEEEEWEEWWEWWEEWWEEEEEWWEWEWEEWWEEWEEWEWWWWEEWEWEWEEEEEEEWEW...
output:
800 640000
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 37ms
memory: 17300kb
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: 13736kb
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: 13688kb
input:
100000 10 10 NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...
output:
1 10
result:
ok 2 lines
Test #11:
score: -6
Wrong Answer
time: 16ms
memory: 13772kb
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%