#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
const ll maxn=1e6+10;
const ll mod =998244353 ;
const ll base=3e18;
ll a[812][812];
ll ax[5]= {-1,0,1,0};
ll ay[5]= {0,1,0,-1};
ll msk[17];
ll cntnw=0;
ll chk[812][812];
ll p,n, m;
ll ans[812][812];
bool dd[maxn];
ll hsh(ll x,ll y)
{
return (x-1)*m+y;
}
ll par[maxn];
ll find_par(ll u)
{
if (par[u]<0)
return u;
return par[u]=find_par(par[u]);
}
void dsu(ll x,ll y)
{
x=find_par(x);
y=find_par(y);
assert(x!=y);
par[x]=y;
}
bool dosth(ll x,ll y)
{
vector<pll> vt;
vt.pb(make_pair(x,y));
chk[x][y]=cntnw;
for (int i=0; i<vt.size(); i++)
{
auto p=vt[i];
int x=p.ff;
int y=p.ss;
for (int j=0; j<4; j++)
{
int x1=x+ax[j];
int y1=y+ay[j];
if (x1>=1&&x1<=n&&y1>=1&&y1<=m&&chk[x1][y1]!=cntnw&&a[x1][y1])
{
ll nw=0;
for (int k=0; k<4; k++)
{
ll x2=x1+ax[k];
ll y2=y1+ay[k];
if (a[x2][y2]&&x2>=1&&x2<=n&&y2>=1&&y2<=m&&chk[x2][y2]==cntnw)
nw+=(1ll<<k);
}
if (a[x1][y1]<=msk[nw])
{
if (find_par(hsh(x1,y1))!=find_par(hsh(x,y)))
{
dsu(find_par(hsh(x,y)),find_par(hsh(x1,y1)));
return true;
}
chk[x1][y1]=cntnw;
vt.pb(make_pair(x1,y1));
}
}
}
}
dd[hsh(x,y)]=1;
for (auto to:vt)
{
ans[to.ff][to.ss]=vt.size();
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
memset(par,-1,sizeof(par));
memset(ans,0x3f,sizeof(ans));
cin>>p>> n>> m;
string s;
cin>> s;
for (int i=0; i<p; i++)
{
if (s[i]=='N')
s[i]='0';
else if (s[i]=='E')
s[i]='1';
else if (s[i]=='S')
s[i]='2';
else
s[i]='3';
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
cin>>a[i][j];
}
}
p+=p;
s+=s;
for (int i=1; i<16; i++)
{
ll pre=-1;
for (int j=0; j<p; j++)
{
ll t=s[j]-'0';
// cout <<t<<endl;
if (i&(1ll<<t))
msk[i]=max(msk[i],j-pre);
else
pre=j;
}
if (msk[i]==p)
msk[i]=base;
// cout<<msk[i]<<" ";
}
//1 2 3 2 2 4 5 1 2 2 4 3 4 5 3000000000000000000
while (1)
{
bool chk=0;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
if (a[i][j]&&!dd[hsh(i,j)]&&find_par(hsh(i,j))==hsh(i,j))
{
cntnw++;
chk|=dosth(i,j);
}
}
}
if (!chk)
break;
}
pll res=make_pair(base,0);
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
if (!a[i][j])
continue;
if (res.ff>ans[i][j])
{
res.ff=ans[i][j];
res.ss=1;
}
else if (res.ff==ans[i][j])
res.ss++;
}
}
cout <<res.ff<<endl;
cout <<res.ss<<endl;
}
Compilation message
virus.cpp: In function 'bool dosth(long long int, long long int)':
virus.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i=0; i<vt.size(); i++)
| ~^~~~~~~~~~
virus.cpp: In function 'int main()':
virus.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen("test.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
13516 KB |
Output is correct |
2 |
Correct |
138 ms |
24052 KB |
Output is correct |
3 |
Correct |
145 ms |
24036 KB |
Output is correct |
4 |
Correct |
150 ms |
24088 KB |
Output is correct |
5 |
Correct |
161 ms |
24192 KB |
Output is correct |
6 |
Correct |
9 ms |
17996 KB |
Output is correct |
7 |
Correct |
238 ms |
24596 KB |
Output is correct |
8 |
Correct |
77 ms |
20140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
13388 KB |
Output is correct |
2 |
Correct |
10 ms |
13772 KB |
Output is correct |
3 |
Correct |
21 ms |
13772 KB |
Output is correct |
4 |
Correct |
11 ms |
13728 KB |
Output is correct |
5 |
Correct |
23 ms |
13656 KB |
Output is correct |
6 |
Correct |
23 ms |
14000 KB |
Output is correct |
7 |
Correct |
7 ms |
13388 KB |
Output is correct |
8 |
Correct |
22 ms |
13924 KB |
Output is correct |
9 |
Correct |
7 ms |
13644 KB |
Output is correct |
10 |
Correct |
10 ms |
13772 KB |
Output is correct |
11 |
Correct |
7 ms |
13740 KB |
Output is correct |
12 |
Correct |
7 ms |
13824 KB |
Output is correct |
13 |
Correct |
21 ms |
14004 KB |
Output is correct |
14 |
Correct |
21 ms |
13988 KB |
Output is correct |
15 |
Correct |
21 ms |
14048 KB |
Output is correct |
16 |
Correct |
21 ms |
14032 KB |
Output is correct |
17 |
Correct |
15 ms |
13884 KB |
Output is correct |
18 |
Correct |
8 ms |
13772 KB |
Output is correct |
19 |
Correct |
22 ms |
14060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
13516 KB |
Output is correct |
2 |
Correct |
138 ms |
24052 KB |
Output is correct |
3 |
Correct |
145 ms |
24036 KB |
Output is correct |
4 |
Correct |
150 ms |
24088 KB |
Output is correct |
5 |
Correct |
161 ms |
24192 KB |
Output is correct |
6 |
Correct |
9 ms |
17996 KB |
Output is correct |
7 |
Correct |
238 ms |
24596 KB |
Output is correct |
8 |
Correct |
77 ms |
20140 KB |
Output is correct |
9 |
Correct |
6 ms |
13388 KB |
Output is correct |
10 |
Correct |
10 ms |
13772 KB |
Output is correct |
11 |
Correct |
21 ms |
13772 KB |
Output is correct |
12 |
Correct |
11 ms |
13728 KB |
Output is correct |
13 |
Correct |
23 ms |
13656 KB |
Output is correct |
14 |
Correct |
23 ms |
14000 KB |
Output is correct |
15 |
Correct |
7 ms |
13388 KB |
Output is correct |
16 |
Correct |
22 ms |
13924 KB |
Output is correct |
17 |
Correct |
7 ms |
13644 KB |
Output is correct |
18 |
Correct |
10 ms |
13772 KB |
Output is correct |
19 |
Correct |
7 ms |
13740 KB |
Output is correct |
20 |
Correct |
7 ms |
13824 KB |
Output is correct |
21 |
Correct |
21 ms |
14004 KB |
Output is correct |
22 |
Correct |
21 ms |
13988 KB |
Output is correct |
23 |
Correct |
21 ms |
14048 KB |
Output is correct |
24 |
Correct |
21 ms |
14032 KB |
Output is correct |
25 |
Correct |
15 ms |
13884 KB |
Output is correct |
26 |
Correct |
8 ms |
13772 KB |
Output is correct |
27 |
Correct |
22 ms |
14060 KB |
Output is correct |
28 |
Correct |
218 ms |
40344 KB |
Output is correct |
29 |
Correct |
136 ms |
23680 KB |
Output is correct |
30 |
Correct |
144 ms |
23928 KB |
Output is correct |
31 |
Correct |
186 ms |
24120 KB |
Output is correct |
32 |
Correct |
175 ms |
24092 KB |
Output is correct |
33 |
Correct |
144 ms |
24024 KB |
Output is correct |
34 |
Correct |
277 ms |
39948 KB |
Output is correct |
35 |
Correct |
156 ms |
29520 KB |
Output is correct |
36 |
Correct |
214 ms |
24016 KB |
Output is correct |
37 |
Correct |
192 ms |
30984 KB |
Output is correct |
38 |
Correct |
193 ms |
40020 KB |
Output is correct |
39 |
Correct |
173 ms |
24312 KB |
Output is correct |
40 |
Correct |
196 ms |
24420 KB |
Output is correct |
41 |
Correct |
123 ms |
24228 KB |
Output is correct |
42 |
Correct |
200 ms |
32648 KB |
Output is correct |
43 |
Correct |
136 ms |
24348 KB |
Output is correct |
44 |
Correct |
81 ms |
20196 KB |
Output is correct |