이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
struct Candidat {
pair<int, int> act, pre;
};
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'};
bool inComp[M][M];
bool cantInf[M][M];
set<pair<int, int>> cfc[M][M];
pair<int, int> acces[M][M], same[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) {
return inComp[adj.x][adj.y];
//act = getCFC(act), adj = getCFC(adj);
//return cfc[act.x][act.y].find(adj) != cfc[act.x][act.y].end();
}
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];
}
bool check(pair<int, int> coo) {
for(int i = 0; i < 4; i++) {
int x = coo.x + dl[i], y = coo.y + dc[i];
if(valid(x, y) && hasAcces(x, y, coo.x, coo.y))
return true;
}
return false;
}
void solve() {
vector<Candidat> candidat;
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++) {
if(check({i, j})) {
candidat.push_back({{i, j}, {i, j}});
} else {
cantInf[i][j] = true;
//cout << "CAN'T " << i << ' ' << j << '\n';
}
}
while(!candidat.empty()) {
auto cand = candidat.back();
candidat.pop_back();
bool nouv = false;
//cout << "CANDIDAT " << cand.act.x << ' ' << cand.act.y << '\n';
//for(pair<int, int> coo : cfc[cand.pre.x][cand.pre.y]) {
for(pair<int, int> coo : cfc[cand.act.x][cand.act.y]) {
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(cantInf[x][y]) {
nouv = false;
cfc[cand.act.x][cand.act.y].insert({x, y});
} else if(getAcces({x, y}) != cand.act) {
//suppr candidat
//cout << " SUPPR\n";
acces[cand.act.x][cand.act.y] = getCFC({x, y});
} else {
//merge de CFC
//cout << " MERGE\n";
auto act = cand.act, 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]);
for(pair<int, int> cas : cfc[pre.x][pre.y])
cfc[act.x][act.y].insert(cas);
same[pre.x][pre.y] = act;
acces[pre.x][pre.y] = act;
candidat.push_back({act, pre});
}
}
}
}
if(nouv) break;
}
//cout << '\n';
if(!nouv) {
//CFC minimale
int sz = (int)cfc[cand.act.x][cand.act.y].size(), cnt = 0;
for(pair<int, int> pii : cfc[cand.act.x][cand.act.y])
if(!cantInf[pii.x][pii.y])
cnt++;
if(mini == sz) nb += cnt;
else if(mini > sz && sz != 1) {
nb = cnt;
mini = sz;
}
}
}
}
void reset() {
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
inComp[i][j] = false;
}
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].insert({i, j});
same[i][j] = acces[i][j] = {i, j};
}
//solve();
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
reset();
int cnt = 0;
vector<pair<int, int>> v;
v.push_back({i, j});
while(!v.empty()) {
auto coo = v.back();
v.pop_back();
if(!inComp[coo.x][coo.y]) {
cnt++;
inComp[coo.x][coo.y] = true;
for(int k = 0; k < 4; k++) {
int x = coo.x + dl[k], y = coo.y + dc[k];
if(valid(x, y) && !inComp[x][y] && hasAcces(x, y, coo.x, coo.y)) {
v.push_back({x, y});
}
}
}
}
if(cnt < mini && cnt != 1) {
mini = cnt;
nb = 1;
} else if(mini == cnt) {
nb++;
}
}
}
cout << mini << '\n' << nb << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |