QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#287126 | #1127. Virus Experiment | whdywjd | 0 | 68ms | 15084kb | C++14 | 4.8kb | 2023-12-19 18:53:04 | 2023-12-19 18:53:05 |
Judging History
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%