Comparar texto

Encontre a diferença entre dois arquivos de texto

Real-time diff
Unified diff
Collapse lines
Highlight change
Syntax highlighting
Ferramentas
Diffchecker Desktop icon
Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Download Diffchecker DesktopLearn more

Untitled diff

Created Diff never expires
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;
}
}
Diffs salvos