Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live

Ocultar sin cambios

Sin ajuste de línea

Vista

Nivel de detalle

Resaltado de sintaxis

Diffchecker Desktop La forma más segura de usar Diffchecker. ¡Obtén la app de Diffchecker Desktop: tus diffs nunca salen de tu computadora!Obtener Desktop

Untitled diff

Creado hace 7 añosEl diff nunca expira

7 eliminaciones

Líneas
Total
Eliminado

Caracteres
Total
Eliminado

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

156 líneas

7 adiciones

Líneas
Total
Añadido

Caracteres
Total
Añadido

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

156 líneas

//1137C. Museums Tour

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define unique(x) (x).erase(std::unique(all(x)), (x).end())

#define cerr cerr && false && std::cerr

typedef std::pair<int,int> pii;

typedef std::vector<int> vi;

typedef std::vector<vi> vvi;

namespace Optimized {

int nVert, nDays, nParts;

vvi next, prev; // lists for adjacent vertices: next - normal direction, prev - reversed direction

vi topOrder, part, vertInPart;

struct State { bool in; int u; };

std::vector<State> stack;

void init(const int n, const int d, const std::vector<pii> &input) {

nVert = n;

nDays = d;

nParts = 0;

next.assign(nVert, {});

prev.assign(nVert, {});

topOrder.clear();

stack.clear();

stack.reserve(2 * nVert * nDays);

for (auto &e : input) {

const int u = e.first-1;

const int v = e.second-1;

next[u].push_back(v);

prev[v].push_back(u);

}

void topsort() {

auto &visited = part;

visited.assign(nVert * nDays, 0);

for (int it = 0; it < nVert * nDays; ++it) {

if (!visited[it]) {

stack.push_back(State{true,it});

while (!stack.empty()) {

auto in = stack.back().in;

auto u = stack.back().u;

stack.pop_back();

if (in) {

if (visited[u]) { continue; }

visited[u] = 1;

stack.push_back(State{false,u});

int currDay = u / nVert, currVert = u % nVert;

for (int v : next[currVert]) {

v += (currDay + 1) % nDays * nVert;

stack.push_back(State{true,v});

}

} else {

topOrder.push_back(u);

}

std::reverse(all(topOrder));

}

void components() {

part.assign(nVert * nDays, 0);

nParts = 0;

for (int u : topOrder) {

if (!part[u]) {

nParts++;

part[u] = nParts;

assert(stack.empty());

stack.push_back(State{true,u});

while (!stack.empty()) {

auto curr = stack.back().u; stack.pop_back();

int currVert = curr % nVert;

int currDay = curr / nVert;

for (int v : prev[currVert]) {

v += (currDay-1+nDays) % nDays * nVert;

if (!part[v]) {

part[v] = nParts;

stack.push_back(State{true,v});

}

void count(const std::vector<std::string>& isOpen) {

vertInPart.assign(1+nParts, 0);

for (int v = 0; v < nVert; ++v) {

std::vector<int> incParts;

for (int day = 0; day < nDays; ++day) {

if (isOpen[v][day] == '1') {

int u = day * nVert + v;

incParts.push_back(part[u]);

}

std::sort(all(incParts));

unique(incParts);

for (int p : incParts) {

vertInPart[p]++;

}

int solve(const int n, const int d, const std::vector<pii>& inEdges, const std::vector<std::string>& isOpen) {

init(n, d, inEdges);

topsort();

components();

count(isOpen);

vi dp(1+nParts, 0);

std::reverse(all(topOrder));

for (int u : topOrder) {

const int pu = part[u];

dp[pu] = std::max(dp[pu], vertInPart[pu]);

const int currVert = 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];

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));

return dp[part[0]];

}

template<typename T1, typename T2>

std::istream& operator>>(std::istream& is, std::pair<T1, T2>& pair) {

return is >> pair.first >> pair.second;

}

template<typename T>

std::istream& operator>>(std::istream& is, std::vector<T>& vec) {

for (auto &it : vec) { is >> it; }

return is;

}

int main() {

std::ios_base::sync_with_stdio(false); std::cin.tie(0);

int n, m, d;

std::cin >> n >> m >> d;

std::vector<std::string> isOpen(n);

std::vector<pii> inEdges(m);

std::cin >> inEdges >> isOpen;

std::cout << Optimized::solve(n,d,inEdges, isOpen) << std::endl;

return 0;

}

Diferencias guardadas

Texto original

Abrir archivo

//1137C. Museums Tour
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define unique(x) (x).erase(std::unique(all(x)), (x).end())
#define cerr cerr && false && std::cerr
typedef std::pair<int,int> pii;
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;

namespace Optimized {

int nVert, nDays, nParts;

vvi next, prev; // lists for adjacent vertices: next - normal direction, prev - reversed direction

vi topOrder, part, vertInPart;
    
    struct State { bool in; int u; };
    
    std::vector<State> stack;
    
    void init(const int n, const int d, const std::vector<pii> &input) {
        nVert = n;
        nDays = d;
        nParts = 0;
        next.assign(nVert, {});
        prev.assign(nVert, {});
        topOrder.clear();
        stack.clear();
        stack.reserve(2 * nVert * nDays);
        for (auto &e : input) {
            const int u = e.first-1;
            const int v = e.second-1;
            next[u].push_back(v);
            prev[v].push_back(u);
        }
    }    
    
    void topsort() {
        auto &visited = part;
        visited.assign(nVert * nDays, 0);
        for (int it = 0; it < nVert * nDays; ++it) {
            if (!visited[it]) {
                stack.push_back(State{true,it});
                while (!stack.empty()) {
                    auto in = stack.back().in;
                    auto u  = stack.back().u;
                    stack.pop_back();
                    if (in) {
                        if (visited[u]) { continue; }
                        visited[u] = 1;
                        stack.push_back(State{false,u});
                        int currDay = u / nVert, currVert = u % nVert;
                        for (int v : next[currVert]) {
                            v += (currDay + 1) % nDays * nVert;
                            stack.push_back(State{true,v});
                        }
                    } else {
                        topOrder.push_back(u);
                    }
                }
            }
        }
        std::reverse(all(topOrder));
    }
    
    void components() {
        part.assign(nVert * nDays, 0);
        nParts = 0;
        for (int u : topOrder) {
            if (!part[u]) {
                nParts++;
                part[u] = nParts;
                assert(stack.empty());
                stack.push_back(State{true,u});
                while (!stack.empty()) {
                    auto curr = stack.back().u; stack.pop_back();
                    int currVert = curr % nVert;
                    int currDay = curr / nVert;
                    for (int v : prev[currVert]) {
                        v += (currDay-1+nDays) % nDays * nVert;
                        if (!part[v]) {
                            part[v] = nParts;
                            stack.push_back(State{true,v});
                        }
                    }
                }
            }
        }
    }

void count(const std::vector<std::string>& isOpen) {
        vertInPart.assign(1+nParts, 0);
        for (int v = 0; v < nVert; ++v) {
            std::vector<int> incParts;
            for (int day = 0; day < nDays; ++day) {
                if (isOpen[v][day] == '1') {
                    int u = day * nVert + v;
                    incParts.push_back(part[u]);
                }
            }
            std::sort(all(incParts));
            unique(incParts);
            for (int p : incParts) {
                vertInPart[p]++;
            }
        }
    }
    
    int solve(const int n, const int d, const std::vector<pii>& inEdges, const std::vector<std::string>& isOpen) {
        init(n, d, inEdges);
        topsort();
        components();
        count(isOpen);
        vi dp(1+nParts, 0);
        std::reverse(all(topOrder));
        for (int u : topOrder) {
            const int pu = part[u];
            dp[pu] = std::max(dp[pu], vertInPart[pu]);
            const int currVert = u % nVert;
            const int currDay = u / nVert;
            for (int v : prev[currVert]) {
                v += (currDay-1+nDays) % nDays * nVert;
                const int pv = part[v];
                if (pv != pu) {
                    assert(pv < pu);
                    dp[pv] = std::max(dp[pv], dp[pu] + vertInPart[pv]);
                }
            }
        }
        std::reverse(all(topOrder));
        return dp[part[0]];
    }
}

template<typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& pair) {
    return is >> pair.first >> pair.second;
}

template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
    for (auto &it : vec) { is >> it; }
    return is;
}

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(0);
    int n, m, d;
    std::cin >> n >> m >> d;
    std::vector<std::string> isOpen(n);
    std::vector<pii> inEdges(m);
    std::cin >> inEdges >> isOpen;
    std::cout << Optimized::solve(n,d,inEdges, isOpen) << std::endl;
    return 0;
}

Texto modificado

Abrir archivo

namespace Optimized {

int nVert, nDays, nParts;

vvi next, prev; // lists for adjacent vertices: next - normal direction, prev - reversed direction

void count(const std::vector<std::string>& isOpen) {
        vertInPart.assign(1+nParts, 0);
        for (int v = 0; v < nVert; ++v) {
            std::vector<int> incParts;
            for (int day = 0; day < nDays; ++day) {
                if (isOpen[v][day] == '1') {
                    int u = day * nVert + v;
                    incParts.push_back(part[u]);
                }
            }
            std::sort(all(incParts));
            unique(incParts);
            for (int p : incParts) {
                vertInPart[p]++;
            }
        }
    }
    
    int solve(const int n, const int d, const std::vector<pii>& inEdges, const std::vector<std::string>& isOpen) {
        init(n, d, inEdges);
        topsort();
        components();
        count(isOpen);
        vi dp(1+nParts, 0);
        std::reverse(all(topOrder));
        for (int u : topOrder) {
            const int pu = part[u];
            dp[pu] = std::max(dp[pu], vertInPart[pu]);
            const int currVert = u % nVert;
            const int currDay = u / nVert;
            for (int v : next[currVert]) {
                v += (currDay+1) % nDays * nVert;
                const int pv = part[v];
                if (pv != pu) {
                    assert(pv > pu);
                    dp[pu] = std::max(dp[pu], dp[pv] + vertInPart[pu]);
                }
            }
        }
        std::reverse(all(topOrder));
        return dp[part[0]];
    }
}

template<typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& pair) {
    return is >> pair.first >> pair.second;
}

template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
    for (auto &it : vec) { is >> it; }
    return is;
}