이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <random>
#include <algorithm>
#include <cassert>
using namespace std;
#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::cprint(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif
using VI = vector<int>;
using VVI = vector<VI>;
int M, R, C;
string D;
int U[801][801];
int max_runs[1<<4];
const string DIR = "NESW"; // direction wind blows from
int dr[] = {-1, 0, +1, 0};
int dc[] = { 0, +1, 0, -1};
void dfs1(const VVI& G, VI& vis, stack<int>& S, int u) {
vis[u] = true;
for (int v : G[u]) {
if (!vis[v])
dfs1(G, vis, S, v);
}
S.push(u);
}
void dfs2(const VVI& G, VI& vis, VI& comp, int u) {
vis[u] = true;
comp.push_back(u);
for (int v : G[u]) {
if (!vis[v])
dfs2(G, vis, comp, v);
}
}
const int INF = 1e9 + 7;
long long sum_cnt = 0;
VI COMP_IDs;
int best_count;
VI ans;
vector<bool> processed;
int infected_mask[801*801];
void bfs(const VI& sources, VI& vis, int comp_id) {
queue<int> q;
for (int src : sources) {
if (U[src / C][src % C] == 0)
return;
q.push(src);
vis[src] = comp_id;
}
bool ok = true;
VI visited_nodes, changed_infected_masks;
while (!q.empty()) {
int u = q.front(); q.pop();
visited_nodes.push_back(u);
if (int(visited_nodes.size()) > best_count)
break;
// assert(cnt < R*C*2);
int r = u/C, c = u % C;
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 or nr >= R or nc < 0 or nc >= C or U[nr][nc] == 0)
continue;
int v = nr * C + nc;
if (infected_mask[v] == 0)
changed_infected_masks.push_back(v);
infected_mask[v] |= 1<<((d+2)%4);
if ( max_runs[ infected_mask[v] ] < U[nr][nc] )
continue;
if (processed[COMP_IDs[v]]) {
ok = false;
break;
}
if (vis[v] != comp_id) {
q.push(v);
vis[v] = comp_id;
}
}
}
sum_cnt += visited_nodes.size();
if (ok and best_count > int(visited_nodes.size())) {
best_count = visited_nodes.size();
for (int u : visited_nodes)
ans[u] = min(ans[u], best_count);
}
for (int v : changed_infected_masks)
infected_mask[v] = 0;
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> M >> R >> C;
cin >> D;
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c)
cin >> U[r][c];
D += D;
auto matches = [](int mask, char c) -> bool {
size_t d = DIR.find(c);
assert(d != string::npos);
return (mask & (1<<d)) != 0;
};
for (int mask = (1<<4)-1; mask > 0; --mask) {
for (int k = 0, run = 0; k <= int(D.size()); k++) {
if (k == int(D.size()) or not matches(mask, D[k])) {
max_runs[mask] = max(max_runs[mask], run);
run = 0;
}
else
++run;
}
if (max_runs[mask] >= M)
max_runs[mask] = INF;
// DEBUG(mask, max_runs[mask]);
}
const int NUM_NODES = R*C;
auto NODE_ID = [](int r, int c) -> int {
return r*C + c;
};
VVI G(NUM_NODES);
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
if (U[r][c] == 0) continue;
for (int d = 0; d < 4; ++d) {
if (U[r][c] > max_runs[1<<d])
continue;
int pr = r + dr[d], pc = c + dc[d];
if (pr < 0 or pr >= R or pc < 0 or pc >= C or U[pr][pc] == 0)
continue;
G[NODE_ID(pr, pc)].push_back(NODE_ID(r, c));
}
}
}
VI vis(NUM_NODES, false);
stack<int> S;
for (int src = 0; src < NUM_NODES; ++src)
if (!vis[src])
dfs1(G, vis, S, src);
VVI Grev(NUM_NODES);
for (int u = 0; u < NUM_NODES; ++u)
for (int v : G[u])
Grev[v].push_back(u);
vis = VI(NUM_NODES, false);
VVI SCC;
COMP_IDs = VI(NUM_NODES, -1);
while (!S.empty()) {
int u = S.top(); S.pop();
if (!vis[u]) {
VI comp;
dfs2(Grev, vis, comp, u);
int comp_id = SCC.size();
for (int u : comp)
COMP_IDs[u] = comp_id;
SCC.push_back(comp);
}
}
// DEBUG(SCC.size());
/*
auto is_root = [&](int comp_id) -> bool {
for (int u : SCC[comp_id])
for (int v : G[u])
if (COMP_IDs[v] > COMP_IDs[u])
return false;
return true;
};
*/
best_count = INF;
ans = VI(NUM_NODES, INF);
vis = VI(NUM_NODES, INF);
processed = vector<bool>(SCC.size(), false);
VI P(SCC.size());
for (int k = 0; k < (int) SCC.size(); ++k)
P[k] = k;
mt19937 gen( 321 );
shuffle(P.begin(), P.end(), gen);
for (int comp_id : P) {
/*
cerr << comp_id << ":";
for (int u : SCC[comp_id])
cerr << " (" << u/C << ',' << u%C << ")";
cerr << endl;
*/
bfs( SCC[comp_id], vis, comp_id );
processed[comp_id] = true;
}
cout << best_count << '\n';
cout << (best_count < INF ?
count(ans.begin(), ans.end(), best_count) :
0) << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |