Confronta il testo

Trova la differenza tra due file di testo

Editor live

Comprimi invariate

Senza a capo

Layout

Livello di dettaglio

Evidenziazione sintassi

Diffchecker Desktop Il modo più sicuro per usare Diffchecker. Ottieni l'app Diffchecker Desktop: i tuoi diff non lasciano mai il tuo computer!Ottieni Desktop

Untitled diff

Creato 7 anni faIl diff non scade mai

7 rimozioni

Linee
Totale
Rimosso

Caratteri
Totale
Rimosso

Per continuare a utilizzare questa funzione, aggiorna a Diffchecker Pro Visualizza prezzi

156 linee

7 aggiunte

Linee
Totale
Aggiunto

Caratteri
Totale
Aggiunto

Per continuare a utilizzare questa funzione, aggiorna a Diffchecker Pro Visualizza prezzi

156 linee

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

}

Diff salvati

Testo originale

Apri file

//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;
}

Testo modificato

Apri file

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