#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N = 2e5 + 42, M = 805, INF = 1e18 + 42;
int dl[] = {-1, 0, 1, 0},
dc[] = {0, -1, 0, 1};
char ch[N], w[] = {'N', 'W', 'S', 'E'};
pair<int, int> acces[M][M], same[M][M];
vector<pair<int, int>> cfc[M][M], toAdd[M][M];
int m, row, col, mini = INF, nb = 0, maxi[16], u[M][M];
pair<int, int> getCFC(pair<int, int> coo) {
if(same[coo.x][coo.y] == coo)
return coo;
return same[coo.x][coo.y] = getCFC(same[coo.x][coo.y]);
}
pair<int, int> getAcces(pair<int, int> coo) {
if(acces[coo.x][coo.y] == coo)
return coo;
return acces[coo.x][coo.y] = getAcces(acces[coo.x][coo.y]);
}
inline bool valid(int x, int y) {
return -1 < x && x < row && -1 < y && y < col;
}
inline bool sameCFC(pair<int, int> act, pair<int, int> adj) {
act = getCFC(act), adj = getCFC(adj);
return act == adj;
}
inline bool hasAcces(int l, int c, int x, int y) {
int mask = 0;
for(int i = 0; i < 4; i++) {
int adjX = l + dl[i], adjY = c + dc[i];
if(valid(adjX, adjY) && sameCFC({x, y}, {adjX, adjY}))
mask += (1 << i);
}
//cout << " " << u[l][c] << ' ' << maxi[mask] << ' ' << mask << '\n';
return u[l][c] <= maxi[mask];
}
void solve() {
vector<pair<int, int>> candidat;
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
if(u[i][j] != INF)
candidat.push_back({i, j});
while(!candidat.empty()) {
pair<int, int> cand = candidat.back();
candidat.pop_back();
bool nouv = false;
//cout << "CANDIDAT " << cand.x << ' ' << cand.y << '\n';
//for(pair<int, int> coo : cfc[cand.pre.x][cand.pre.y]) {
while(!toAdd[cand.x][cand.y].empty()) {
pair<int, int> coo = toAdd[cand.x][cand.y].back();
toAdd[cand.x][cand.y].pop_back();
if(valid(coo.x, coo.y)) {
//cout << " TEST " << coo.x << ' ' << coo.y << '\n';
for(int i = 0; i < 4 && !nouv; i++) {
int x = coo.x + dl[i], y = coo.y + dc[i];
//cout << " CHECKING " << x << ' ' << y << '\n';
if(valid(x, y) && !sameCFC(coo, {x, y}) && hasAcces(x, y, coo.x, coo.y)) {
nouv = true;
//cout << " NEW\n";
if(getAcces({x, y}) != cand) {
//suppr candidat
//cout << " SUPPR\n";
acces[cand.x][cand.y] = getCFC({x, y});
} else {
//merge de CFC
//cout << " MERGE\n";
auto act = cand, pre = getCFC({x, y});
if(cfc[act.x][act.y].size() < cfc[pre.x][pre.y].size()) {
swap(cfc[pre.x][pre.y], cfc[pre.x][pre.y]);
swap(toAdd[pre.x][pre.y], toAdd[pre.x][pre.y]);
}
for(pair<int, int> cas : cfc[pre.x][pre.y]) {
cfc[act.x][act.y].push_back(cas);
toAdd[act.x][act.y].push_back(cas);
}
toAdd[act.x][act.y].push_back(coo);
same[pre.x][pre.y] = act;
acces[pre.x][pre.y] = act;
candidat.push_back(act);
}
}
}
}
if(nouv) break;
}
//cout << '\n';
if(!nouv) {
//CFC minimale
int sz = (int)cfc[cand.x][cand.y].size();
if(mini == sz) nb += sz;
else if(mini > sz) mini = nb = sz;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> row >> col;
for(int i = 0; i < m; i++)
cin >> ch[i];
for(int i = 0; i < m; i++)
ch[i + m] = ch[i];
for(int i = 0; i < 16; i++) {
int len = 0;
for(int j = 0; j < 2*m; j++) {
int wind = 0;
for(int k = 0; k < 4; k++)
if(w[k] == ch[j] && (i & (1 << k)))
wind = 1;
if(wind == 0)
len = 0;
else
len++;
maxi[i] = max(maxi[i], len);
}
if(maxi[i] == 2*m) maxi[i] = N;
}
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++) {
cin >> u[i][j];
if(u[i][j] == 0)
u[i][j] = INF;
cfc[i][j].push_back({i, j});
toAdd[i][j].push_back({i, j});
same[i][j] = acces[i][j] = {i, j};
}
solve();
cout << mini << '\n' << nb << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
31060 KB |
Output is correct |
2 |
Correct |
229 ms |
113904 KB |
Output is correct |
3 |
Correct |
221 ms |
116156 KB |
Output is correct |
4 |
Correct |
167 ms |
113776 KB |
Output is correct |
5 |
Correct |
216 ms |
116256 KB |
Output is correct |
6 |
Correct |
20 ms |
40388 KB |
Output is correct |
7 |
Correct |
386 ms |
120368 KB |
Output is correct |
8 |
Correct |
117 ms |
67284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
30900 KB |
Output is correct |
2 |
Correct |
27 ms |
31196 KB |
Output is correct |
3 |
Correct |
47 ms |
31164 KB |
Output is correct |
4 |
Correct |
26 ms |
31188 KB |
Output is correct |
5 |
Correct |
48 ms |
31052 KB |
Output is correct |
6 |
Correct |
48 ms |
32204 KB |
Output is correct |
7 |
Correct |
15 ms |
30872 KB |
Output is correct |
8 |
Correct |
48 ms |
31580 KB |
Output is correct |
9 |
Correct |
16 ms |
31572 KB |
Output is correct |
10 |
Correct |
27 ms |
31188 KB |
Output is correct |
11 |
Correct |
16 ms |
31676 KB |
Output is correct |
12 |
Correct |
17 ms |
31832 KB |
Output is correct |
13 |
Correct |
46 ms |
31948 KB |
Output is correct |
14 |
Correct |
47 ms |
32016 KB |
Output is correct |
15 |
Correct |
45 ms |
31932 KB |
Output is correct |
16 |
Correct |
46 ms |
31948 KB |
Output is correct |
17 |
Correct |
33 ms |
31808 KB |
Output is correct |
18 |
Correct |
17 ms |
31700 KB |
Output is correct |
19 |
Correct |
49 ms |
31956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
31060 KB |
Output is correct |
2 |
Correct |
229 ms |
113904 KB |
Output is correct |
3 |
Correct |
221 ms |
116156 KB |
Output is correct |
4 |
Correct |
167 ms |
113776 KB |
Output is correct |
5 |
Correct |
216 ms |
116256 KB |
Output is correct |
6 |
Correct |
20 ms |
40388 KB |
Output is correct |
7 |
Correct |
386 ms |
120368 KB |
Output is correct |
8 |
Correct |
117 ms |
67284 KB |
Output is correct |
9 |
Correct |
16 ms |
30900 KB |
Output is correct |
10 |
Correct |
27 ms |
31196 KB |
Output is correct |
11 |
Correct |
47 ms |
31164 KB |
Output is correct |
12 |
Correct |
26 ms |
31188 KB |
Output is correct |
13 |
Correct |
48 ms |
31052 KB |
Output is correct |
14 |
Correct |
48 ms |
32204 KB |
Output is correct |
15 |
Correct |
15 ms |
30872 KB |
Output is correct |
16 |
Correct |
48 ms |
31580 KB |
Output is correct |
17 |
Correct |
16 ms |
31572 KB |
Output is correct |
18 |
Correct |
27 ms |
31188 KB |
Output is correct |
19 |
Correct |
16 ms |
31676 KB |
Output is correct |
20 |
Correct |
17 ms |
31832 KB |
Output is correct |
21 |
Correct |
46 ms |
31948 KB |
Output is correct |
22 |
Correct |
47 ms |
32016 KB |
Output is correct |
23 |
Correct |
45 ms |
31932 KB |
Output is correct |
24 |
Correct |
46 ms |
31948 KB |
Output is correct |
25 |
Correct |
33 ms |
31808 KB |
Output is correct |
26 |
Correct |
17 ms |
31700 KB |
Output is correct |
27 |
Correct |
49 ms |
31956 KB |
Output is correct |
28 |
Correct |
327 ms |
152848 KB |
Output is correct |
29 |
Correct |
190 ms |
114124 KB |
Output is correct |
30 |
Correct |
202 ms |
114156 KB |
Output is correct |
31 |
Correct |
276 ms |
120840 KB |
Output is correct |
32 |
Correct |
247 ms |
122768 KB |
Output is correct |
33 |
Correct |
171 ms |
113840 KB |
Output is correct |
34 |
Correct |
401 ms |
195916 KB |
Output is correct |
35 |
Correct |
221 ms |
111200 KB |
Output is correct |
36 |
Correct |
331 ms |
136600 KB |
Output is correct |
37 |
Correct |
328 ms |
159000 KB |
Output is correct |
38 |
Correct |
295 ms |
147828 KB |
Output is correct |
39 |
Correct |
263 ms |
115260 KB |
Output is correct |
40 |
Correct |
293 ms |
116632 KB |
Output is correct |
41 |
Correct |
158 ms |
114060 KB |
Output is correct |
42 |
Correct |
382 ms |
146804 KB |
Output is correct |
43 |
Correct |
206 ms |
114172 KB |
Output is correct |
44 |
Correct |
124 ms |
67228 KB |
Output is correct |