QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#816844#1127. Virus Experimentnullptr_qwq0 49ms25784kbC++142.7kb2024-12-16 18:34:572024-12-16 18:34:58

Judging History

This is the latest submission verdict.

  • [2024-12-16 18:34:58]
  • Judged
  • Verdict: 0
  • Time: 49ms
  • Memory: 25784kb
  • [2024-12-16 18:34:57]
  • Submitted

answer

// Problem: #3155. 「JOI Open 2019」病毒实验
// Contest: LibreOJ
// URL: https://loj.ac/p/3155
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=1000005,NR=805;
int k,n,m,a[NR][NR],fa[maxn];
inline int id(int x,int y){ return (x-1)*n+y; }
inline pii decode(int u){ return mkp((u-1)/m+1,((u-1)%m)+1); }
inline bool in_matrix(int x,int y){ return (x>0&&x<=n&&y>0&&y<=m); }
inline int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }
string virus_wind; 
int q[maxn],st[NR][NR],nxt[maxn],to[NR][NR];
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void solve(){
	cin>>k>>n>>m>>virus_wind,virus_wind+=virus_wind;
	vector<int>cur(16,0),T(16,0);
	for(char &c:virus_wind){
		int d=0;
		for(;c!="NSWE"[d];++d);
		F(s,1,15)if((s>>d)&1)++cur[s]; else chkmax(T[s],cur[s]),cur[s]=0;
	}
	F(s,1,15)chkmax(T[s],cur[s]);
	F(i,1,n)F(j,1,m)cin>>a[i][j],chkmin(a[i][j],k);
	F(i,1,n*m)fa[i]=i;
	F(i,1,n)F(j,1,m)if(!a[i][j])a[i][j]=inf,fa[id(i,j)]=0;
	int ans=inf,cnt=0;
	for(;;){
		vector<int>vec;
		F(u,1,n*m)if(find(u)==u)vec.push_back(u);
		if(vec.empty())break;
		for(int u:vec){
			int qL=1,qR=0; auto [x,y]=decode(u);
			q[++qR]=u,st[x][y]=-1,nxt[u]=u;
			while(qL<=qR){
				auto [x,y]=decode(q[qL++]);
				F(d,0,3){
					const int nx=x+dx[d],ny=y+dy[d],v=id(nx,ny);
					if(!in_matrix(nx,ny))continue;
					if(st[nx][ny]==-1||T[st[nx][ny]|=(1<<d)]<a[nx][ny])continue;
					st[nx][ny]=-1;
					if(find(v)==u)q[++qR]=v;
					else{ nxt[u]=v; break; }
				}
				if(nxt[u]^u)break;
			}
			if(nxt[u]==u){
				if(qR<ans)ans=qR,cnt=1;
				else if(qR==ans)++cnt;
				fa[u]=0;
			}
			F(i,1,qR){
				auto [x,y]=decode(q[i]);
				st[x][y]=0;
				F(d,0,3)st[x+dx[d]][y+dy[d]]=0;
			}
		}
		for(int u:vec)fa[find(u)]=find(nxt[u]);
	}
	cout<<ans<<'\n'<<(ans*cnt);
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

53768 10 50
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
10

result:

ok 2 lines

Test #2:

score: 14
Accepted
time: 44ms
memory: 25784kb

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: 14
Accepted
time: 43ms
memory: 22336kb

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: 14
Accepted
time: 33ms
memory: 21972kb

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
Accepted
time: 49ms
memory: 23056kb

input:

9999 800 800
WWWEEWEEWEWEEEWEEEWWWEWWEEEEEWEEEWWEWWWEWEWEWEEEWWWWWEWEEEEEEWEEWWEWWEEEEWEWWEWWWEEEWWEEWEWWWEWWEWWEEEWWWEWEEWWEWEWWWEWWWEEEWWEEEWWEEEWWWWEWWEWEWWWWEEWEEEWEWWEWEEWEWEEEWEWEEEWWWWEEEEWWWWWWEWWWEWEWWWEWEWWWEWWEEEEWWEEEEEWEWEWWWEWEEEEWEEEEWEEWEEEEEWEWWEEEWWEEEWEEEEWWEWWEEWEEWEWWEWWWEWEEEWE...

output:

1
639810

result:

ok 2 lines

Test #6:

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

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
800

result:

wrong answer 2nd lines differ - expected: '392', found: '800'

Subtask #2:

score: 0
Wrong Answer

Test #9:

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

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: 6
Accepted
time: 4ms
memory: 14036kb

input:

100000 10 10
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN...

output:

1
10

result:

ok 2 lines

Test #11:

score: 6
Accepted
time: 2ms
memory: 13928kb

input:

100000 11 11
SWNESSSWNSEWNSNESSNWEWEWNSNNSWSSWSEEWNENWSWNNEWWSWNSESSEWENNESSENEEEESEESEWENEWSNSNNSSNNSWSNNSNESWEWSENNSESEEWWNESSNNWWSNWNNWNWNWWSEENNNWESSWNWNSEWWNWNNWSWSEWSENSNWNWNNEESSSENWWESSWEESWWENSSENWNNEESWENWSSSWEEWNWEWNNENNWSWEWSNNEESESNWNSEEENWWESSWEEWWSWESSNNEEWWNSSWSNEWSENSNNSENNSSNSSEEEE...

output:

27
27

result:

ok 2 lines

Test #12:

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

input:

100000 10 10
EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE...

output:

1
16

result:

ok 2 lines

Test #13:

score: 6
Accepted
time: 2ms
memory: 13968kb

input:

100000 1 1
WWSSSWEEEEESSNSSSSENWSESSNSWWSWESWSEEWSNSSEESSWESNNNENENWEENSSSSSNENESEESEWWSNNWSEWSWNWESSWNWSEESNSWSWENWEWNWESEWSSNSWENEWNNSWEEWWSSSWNSNWWWNSSWSSNSENESENNNENWESSENNEWENWEENWNWSSSWWWSNWESWEESNNNESNNEESNEWSSNNSSWSSESNSNNWENENEWWWSEESNWEWWNWNNSSNEEWSWNSWEESNSNSNEWNNWWWWSSWSWWESWWENSENWNWNWN...

output:

1
1

result:

ok 2 lines

Test #14:

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

input:

100000 50 50
ENWNNWEESNSNSSESSWNEWWESNWEENNEEWWEWNNESSSEWSWNWEWSSNEEWNSEWSSWNESWSWESEWWSENEWESEWSWSNNWWESSSWSSSESESNSSNESSSWSNWSSSENSWWNWNWNNNSNSNSEENWESENEENNESENSENNWEEESENWSESWSNWNNNSNSNWWENWEEEWSNWWEWSWNSEEEWEWWNSWNNNWWENSNSWWSNNWESNSSSWWNSEWSNWNEEESSEWEESENEESWSNNWSNESEESWEESNWSEEWWSSWESENESSSE...

output:

2500
2500

result:

ok 2 lines

Test #15:

score: 6
Accepted
time: 1ms
memory: 14104kb

input:

100 10 10
NENNWNSNNEWNENENNWWNEWNSNWWSSSNSNESSESWESSNNNNEWSWESNSNWSENWNSESNENWSWEWWWNSNWNWESNSESENNWNNWSSWSNSE
2 1 4 1 4 2 1 3 2 4
1 4 4 4 3 3 4 2 2 1
1 3 1 4 2 2 1 4 2 2
2 3 4 3 3 3 1 2 4 1
2 2 3 4 3 4 4 1 3 4
1 4 4 3 4 4 1 4 4 2
1 4 3 4 1 1 3 3 4 3
4 4 1 2 3 3 2 3 4 4
2 4 2 1 1 3 4 2 4 4
2 1 2 3 4...

output:

1
1

result:

ok 2 lines

Test #16:

score: 0
Wrong Answer
time: 5ms
memory: 13996kb

input:

100000 50 2
ESNNNSWNNESEWSWWWSENWENSWSNSENSWSENWWNEENNWWNESWNWSEWSWWNSSWSSNENSWWWEEEEENSNWWNNESEWSSNSEEENWWNWWNEENSENWSWEWWNNWWNESSSNWNWWSEWEESESNEEEWNNWWEEEESWSEWWNNSNENWWSEEWNWSNWWEEWNSNWWWWWNWWNNSENNEWSEWENSSSSNWSSSNWSNSNEWESEESWWSEEWWWNWWNESNSNSSNEEWSSENNNEEENSNEEEESNSWNNESEENNEESNSSWENSWSWSNSEE...

output:

1000000000
0

result:

wrong answer 1st lines differ - expected: '46', found: '1000000000'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%