oj.uz

답안 #593427

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
593427 2022-07-11T07:27:37 Z haojiandan 바이러스 (JOI19_virus) C++14
100 / 100
 798 ms 141876 KB 
// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
const int INF=1e9;
const int maxn=810;
const int maxm=maxn*maxn;
char s[200010];
int len,n,m,d[maxn][maxn];
int mx[16],dy[300];
int fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool vis[maxn][maxn];
int msk[maxn][maxn];
pair<int,int> q[maxm];
int qq[maxm];
int hd,tl,flag;
vector<pair<int,int> > V;
int pos[maxn][maxn],tot;
pair<int,int> p[maxm];
int mn=INF,cnt;
vector<int> G[maxm];
int calc(int x,int y,int id) {
	V.clear(); V.push_back(MP(x,y));
	q[hd=tl=1]=MP(x,y); vis[x][y]=1;
	while (hd<=tl) {
		x=q[hd].first,y=q[hd].second,hd++;
		for (int i=0;i<4;i++) {
			int a=x+fx[i][0],b=y+fx[i][1];
			if (1<=a&&a<=n&&1<=b&&b<=m&&!vis[a][b]&&d[a][b]) {
				msk[a][b]|=(1<<((i+2)%4));
				V.push_back(MP(a,b));
				if (mx[msk[a][b]]>=d[a][b]) {
				//	printf("  %d %d\n",id,pos[a][b]);
					G[id].push_back(pos[a][b]);
					if (pos[a][b]<id) goto E;
					q[++tl]=MP(a,b),vis[a][b]=1;
				}
			}
		}
	}
	E:
	for (pair<int,int> &A : V) msk[A.first][A.second]=vis[A.first][A.second]=0;
	return tl;
}
int dfn[maxm],low[maxm],id;
int st[maxm],top;
int bel[maxm],col;
int sz[maxm];
void tarjan(int x) {
	dfn[x]=low[x]=++id;
	st[++top]=x;
	for (int v : G[x]) {
		if (!dfn[v]) {
			tarjan(v);
			low[x]=min(low[x],low[v]);
		} else if (!bel[v]) low[x]=min(low[x],dfn[v]);
	}
	if (dfn[x]==low[x]) {
		bel[x]=++col; sz[col]=1;
		while(st[top]!=x) {
			bel[st[top]]=col; sz[col]++;
			--top;
		}
		--top;
	}
}
int out[maxm];
vector<int> H[maxm];
int main() {
	scanf("%d %d %d %s",&len,&n,&m,s+1);
	dy['W']=3,dy['N']=0,dy['E']=1,dy['S']=2;
	int all=0; flag=1;
	for (int i=1;i<=len;i++) s[i+len]=s[i],all|=(1<<dy[s[i]]);
	for (int t=0;t<16;t++) {
		if ((t&all)==all) { mx[t]=INF; continue; }
		int cnt=0;
		for (int i=1;i<=len*2;i++) {
			if (t>>dy[s[i]]&1) cnt++,mx[t]=max(mx[t],cnt); else cnt=0;
		}
	}
	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {
		read(d[i][j]);
		if (d[i][j]) p[++tot]=MP(i,j);
	}
	random_shuffle(p+1,p+tot+1);
	for (int i=1;i<=tot;i++) pos[p[i].first][p[i].second]=i;
	all=0;
	for (int i=1;i<=tot;i++) {
		all+=calc(p[i].first,p[i].second,i);
	}
//	printf("%d\n",all);
	for (int i=1;i<=tot;i++) if (!dfn[i]) tarjan(i);
	for (int i=1;i<=tot;i++) for (int &j : G[i]) if (bel[i]!=bel[j]) out[bel[i]]++;
	for (int i=1;i<=tot;i++) if (out[bel[i]]==0) {
		int res=sz[bel[i]];
		if (mn==res) cnt++; else if (res<mn) mn=res,cnt=1;
		//printf("res=%d %d\n",res,i);
		//assert(res==calc(p[i].first,p[i].second,0));
	}
	printf("%d\n%d\n",mn,cnt);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Compilation message

virus.cpp: In function 'int main()':
virus.cpp:84:56: warning: array subscript has type 'char' [-Wchar-subscripts]
   84 |  for (int i=1;i<=len;i++) s[i+len]=s[i],all|=(1<<dy[s[i]]);
      |                                                     ~~~^
virus.cpp:89:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |    if (t>>dy[s[i]]&1) cnt++,mx[t]=max(mx[t],cnt); else cnt=0;
      |              ~~~^
virus.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d %d %d %s",&len,&n,&m,s+1);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 31408 KB Output is correct
2 Correct 266 ms 70972 KB Output is correct
3 Correct 599 ms 95396 KB Output is correct
4 Correct 597 ms 94008 KB Output is correct
5 Correct 140 ms 58700 KB Output is correct
6 Correct 20 ms 37028 KB Output is correct
7 Correct 598 ms 92740 KB Output is correct
8 Correct 63 ms 43580 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 31316 KB Output is correct
2 Correct 18 ms 31572 KB Output is correct
3 Correct 32 ms 31572 KB Output is correct
4 Correct 20 ms 31524 KB Output is correct
5 Correct 32 ms 31444 KB Output is correct
6 Correct 31 ms 32324 KB Output is correct
7 Correct 16 ms 31304 KB Output is correct
8 Correct 30 ms 31952 KB Output is correct
9 Correct 18 ms 31912 KB Output is correct
10 Correct 19 ms 31572 KB Output is correct
11 Correct 17 ms 31828 KB Output is correct
12 Correct 18 ms 31992 KB Output is correct
13 Correct 34 ms 32200 KB Output is correct
14 Correct 37 ms 32204 KB Output is correct
15 Correct 29 ms 32212 KB Output is correct
16 Correct 31 ms 32144 KB Output is correct
17 Correct 25 ms 32012 KB Output is correct
18 Correct 18 ms 31892 KB Output is correct
19 Correct 31 ms 32076 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 31408 KB Output is correct
2 Correct 266 ms 70972 KB Output is correct
3 Correct 599 ms 95396 KB Output is correct
4 Correct 597 ms 94008 KB Output is correct
5 Correct 140 ms 58700 KB Output is correct
6 Correct 20 ms 37028 KB Output is correct
7 Correct 598 ms 92740 KB Output is correct
8 Correct 63 ms 43580 KB Output is correct
9 Correct 16 ms 31316 KB Output is correct
10 Correct 18 ms 31572 KB Output is correct
11 Correct 32 ms 31572 KB Output is correct
12 Correct 20 ms 31524 KB Output is correct
13 Correct 32 ms 31444 KB Output is correct
14 Correct 31 ms 32324 KB Output is correct
15 Correct 16 ms 31304 KB Output is correct
16 Correct 30 ms 31952 KB Output is correct
17 Correct 18 ms 31912 KB Output is correct
18 Correct 19 ms 31572 KB Output is correct
19 Correct 17 ms 31828 KB Output is correct
20 Correct 18 ms 31992 KB Output is correct
21 Correct 34 ms 32200 KB Output is correct
22 Correct 37 ms 32204 KB Output is correct
23 Correct 29 ms 32212 KB Output is correct
24 Correct 31 ms 32144 KB Output is correct
25 Correct 25 ms 32012 KB Output is correct
26 Correct 18 ms 31892 KB Output is correct
27 Correct 31 ms 32076 KB Output is correct
28 Correct 737 ms 141876 KB Output is correct
29 Correct 794 ms 141468 KB Output is correct
30 Correct 703 ms 117260 KB Output is correct
31 Correct 701 ms 104240 KB Output is correct
32 Correct 665 ms 102576 KB Output is correct
33 Correct 429 ms 79556 KB Output is correct
34 Correct 754 ms 130112 KB Output is correct
35 Correct 592 ms 111844 KB Output is correct
36 Correct 661 ms 93496 KB Output is correct
37 Correct 798 ms 126328 KB Output is correct
38 Correct 679 ms 139056 KB Output is correct
39 Correct 382 ms 78012 KB Output is correct
40 Correct 372 ms 78284 KB Output is correct
41 Correct 420 ms 75896 KB Output is correct
42 Correct 633 ms 110288 KB Output is correct
43 Correct 731 ms 117548 KB Output is correct
44 Correct 74 ms 43708 KB Output is correct