QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#287125 | #1127. Virus Experiment | whdywjd | 0 | 0ms | 11256kb | C++14 | 4.8kb | 2023-12-19 18:51:55 | 2023-12-19 18:51:56 |
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_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;
}
详细
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%