Untitled diff
6 removals
156 lines
6 additions
156 lines
//1137C. Museums Tour
//1137C. Museums Tour
#include <bits/stdc++.h>
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define all(x) (x).begin(), (x).end()
#define unique(x) (x).erase(std::unique(all(x)), (x).end())
#define unique(x) (x).erase(std::unique(all(x)), (x).end())
#define cerr cerr && false && std::cerr
#define cerr cerr && false && std::cerr
typedef std::pair<int,int> pii;
typedef std::pair<int,int> pii;
typedef std::vector<int> vi;
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::vector<vi> vvi;
namespace Optimized {
namespace Optimized {
int nVert, nDays, nParts;
int nVert, nDays, nParts;
vvi next, prev; // lists for adjacent vertices: next - normal direction, prev - reversed direction
vvi next, prev; // lists for adjacent vertices: next - normal direction, prev - reversed direction
vi topOrder, part, vertInPart;
vi topOrder, part, vertInPart;
struct State { bool in; int u; };
struct State { bool in; int u; };
std::vector<State> stack;
std::vector<State> stack;
void init(const int n, const int d, const std::vector<pii> &input) {
void init(const int n, const int d, const std::vector<pii> &input) {
nVert = n;
nVert = n;
nDays = d;
nDays = d;
nParts = 0;
nParts = 0;
next.assign(nVert, {});
next.assign(nVert, {});
prev.assign(nVert, {});
prev.assign(nVert, {});
topOrder.clear();
topOrder.clear();
stack.clear();
stack.clear();
stack.reserve(2 * nVert * nDays);
stack.reserve(2 * nVert * nDays);
for (auto &e : input) {
for (auto &e : input) {
const int u = e.first-1;
const int u = e.first-1;
const int v = e.second-1;
const int v = e.second-1;
next[u].push_back(v);
next[u].push_back(v);
prev[v].push_back(u);
prev[v].push_back(u);
}
}
}
}
void topsort() {
void topsort() {
auto &visited = part;
auto &visited = part;
visited.assign(nVert * nDays, 0);
visited.assign(nVert * nDays, 0);
for (int it = 0; it < nVert * nDays; ++it) {
for (int it = 0; it < nVert * nDays; ++it) {
if (!visited[it]) {
if (!visited[it]) {
stack.push_back(State{true,it});
stack.push_back(State{true,it});
while (!stack.empty()) {
while (!stack.empty()) {
auto in = stack.back().in;
auto in = stack.back().in;
auto u = stack.back().u;
auto u = stack.back().u;
stack.pop_back();
stack.pop_back();
if (in) {
if (in) {
if (visited[u]) { continue; }
if (visited[u]) { continue; }
visited[u] = 1;
visited[u] = 1;
stack.push_back(State{false,u});
stack.push_back(State{false,u});
int currDay = u / nVert, currVert = u % nVert;
int currDay = u / nVert, currVert = u % nVert;
for (int v : next[currVert]) {
for (int v : next[currVert]) {
v += (currDay + 1) % nDays * nVert;
v += (currDay + 1) % nDays * nVert;
stack.push_back(State{true,v});
stack.push_back(State{true,v});
}
}
} else {
} else {
topOrder.push_back(u);
topOrder.push_back(u);
}
}
}
}
}
}
}
}
std::reverse(all(topOrder));
std::reverse(all(topOrder));
}
}
void components() {
void components() {
part.assign(nVert * nDays, 0);
part.assign(nVert * nDays, 0);
nParts = 0;
nParts = 0;
for (int u : topOrder) {
for (int u : topOrder) {
if (!part[u]) {
if (!part[u]) {
nParts++;
nParts++;
part[u] = nParts;
part[u] = nParts;
assert(stack.empty());
assert(stack.empty());
stack.push_back(State{true,u});
stack.push_back(State{true,u});
while (!stack.empty()) {
while (!stack.empty()) {
auto curr = stack.back().u; stack.pop_back();
auto curr = stack.back().u; stack.pop_back();
int currVert = curr % nVert;
int currVert = curr % nVert;
int currDay = curr / nVert;
int currDay = curr / nVert;
for (int v : prev[currVert]) {
for (int v : prev[currVert]) {
v += (currDay-1+nDays) % nDays * nVert;
v += (currDay-1+nDays) % nDays * nVert;
if (!part[v]) {
if (!part[v]) {
part[v] = nParts;
part[v] = nParts;
stack.push_back(State{true,v});
stack.push_back(State{true,v});
}
}
}
}
}
}
}
}
}
}
}
}
void count(const std::vector<std::string>& isOpen) {
void count(const std::vector<std::string>& isOpen) {
vertInPart.assign(1+nParts, 0);
vertInPart.assign(1+nParts, 0);
for (int v = 0; v < nVert; ++v) {
for (int v = 0; v < nVert; ++v) {
std::vector<int> incParts;
std::vector<int> incParts;
for (int day = 0; day < nDays; ++day) {
for (int day = 0; day < nDays; ++day) {
if (isOpen[v][day] == '1') {
if (isOpen[v][day] == '1') {
int u = day * nVert + v;
int u = day * nVert + v;
incParts.push_back(part[u]);
incParts.push_back(part[u]);
}
}
}
}
std::sort(all(incParts));
std::sort(all(incParts));
unique(incParts);
unique(incParts);
for (int p : incParts) {
for (int p : incParts) {
vertInPart[p]++;
vertInPart[p]++;
}
}
}
}
}
}
int solve(const int n, const int d, const std::vector<pii>& inEdges, const std::vector<std::string>& isOpen) {
int solve(const int n, const int d, const std::vector<pii>& inEdges, const std::vector<std::string>& isOpen) {
init(n, d, inEdges);
init(n, d, inEdges);
topsort();
topsort();
components();
components();
count(isOpen);
count(isOpen);
vi dp(1+nParts, 0);
vi dp(1+nParts, 0);
std::reverse(all(topOrder));
std::reverse(all(topOrder));
for (int u : topOrder) {
for (int u : topOrder) {
const int pu = part[u];
const int pu = part[u];
dp[pu] = std::max(dp[pu], vertInPart[pu]);
dp[pu] = std::max(dp[pu], vertInPart[pu]);
const int currVert = u % nVert;
const int currVert = u % nVert;
const int currDay = u / nVert;
const int currDay = u / nVert;
for (int v : prev[currVert]) {
for (int v : next[currVert]) {
v += (currDay-1+nDays) % nDays * nVert;
v += (currDay+1) % nDays * nVert;
const int pv = part[v];
const int pv = part[v];
if (pv != pu) {
if (pv != pu) {
assert(pv < pu);
assert(pv > pu);
dp[pv] = std::max(dp[pv], dp[pu] + vertInPart[pv]);
dp[pu] = std::max(dp[pu], dp[pv] + vertInPart[pu]);
}
}
}
}
}
}
std::reverse(all(topOrder));
std::reverse(all(topOrder));
return dp[part[0]];
return dp[part[0]];
}
}
}
}
template<typename T1, typename T2>
template<typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& pair) {
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& pair) {
return is >> pair.first >> pair.second;
return is >> pair.first >> pair.second;
}
}
template<typename T>
template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
for (auto &it : vec) { is >> it; }
for (auto &it : vec) { is >> it; }
return is;
return is;
}
}
int main() {
int main() {
std::ios_base::sync_with_stdio(false); std::cin.tie(0);
std::ios_base::sync_with_stdio(false); std::cin.tie(0);
int n, m, d;
int n, m, d;
std::cin >> n >> m >> d;
std::cin >> n >> m >> d;
std::vector<std::string> isOpen(n);
std::vector<std::string> isOpen(n);
std::vector<pii> inEdges(m);
std::vector<pii> inEdges(m);
std::cin >> inEdges >> isOpen;
std::cin >> inEdges >> isOpen;
std::cout << Optimized::solve(n,d,inEdges, isOpen) << std::endl;
std::cout << Optimized::solve(n,d,inEdges, isOpen) << std::endl;
return 0;
return 0;
}
}