Submission #602390

#	Time	Username	Problem	Language	Result	Execution time	Memory
602390		verngutz	Aesthetic (NOI20_aesthetic)	C++17	0 / 100	518 ms	109040 KiB

Aesthetic

#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
struct edge {
    int u, v;
    edge reverse() const { return {v, u}; }
    friend ostream& operator<<(ostream& os, const edge& e) {
        return os << "{u: " << e.u << ", v: " << e.v << "}";
    }
};
template <bool Directed, typename TEdge, bool Index> struct graph {
    using EType = TEdge;
    vector<TEdge> edges;
    vector<vector<int>> adj;
    graph(int n) : adj(n + Index) {}
    graph(int n, int m) : graph(n) { edges.reserve(m << not Directed); }
    TEdge& operator()(int e) { return edges[e]; }
    vector<int>& operator[](int u) { return adj[u]; }
    int size() { return adj.size() - Index; }
    void append(int u, const TEdge& e) {
        adj[u].push_back(edges.size());
        edges.push_back(e);
    }
    void add_edge(const TEdge& e) {
        append(e.u, e);
        if(not Directed) append(e.v, e.reverse());
    }
};
template <typename TEdge, bool Index> pair<vector<int>, vector<vector<int>>> find_2eccs(graph<0, TEdge, Index>& g) {
    vector<int> vis(g.adj.size()), low(g.adj.size()), cut_edge(g.edges.size()), s;
    vector<vector<int>> _2eccs = {};
    int timer = 1;
    function<void(int, int)> dfs = [&](int u, int from) {
        vis[u] = low[u] = timer++;
        s.push_back(u);
        for(int e : g[u]) {
            if(not vis[g(e).v]) {
                dfs(g(e).v, e & ~1);
                if(vis[u] < low[g(e).v]) {
                    cut_edge[e] = cut_edge[e ^ 1] = true;
                    _2eccs.push_back(vector<int>());
                    do {
                        _2eccs.back().push_back(s.back()), s.pop_back();
                    } while(_2eccs.back().back() != g(e).v);
                }
                low[u] = min(low[u], low[g(e).v]);
            } else if((e & ~1) != from and vis[u] > vis[g(e).v]) {
                low[u] = min(low[u], vis[g(e).v]);
            }
        }
    };
    for(int u = Index; u < g.adj.size(); u++) if(not vis[u]) {
        dfs(u, -1);
        _2eccs.push_back(vector<int>());
        while(not s.empty()) {
            _2eccs.back().push_back(s.back()), s.pop_back();
        }
    }
    return {move(cut_edge), move(_2eccs)};
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    graph<0, edge, 1> g(n, m);
    edge last_edge;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.add_edge(last_edge = {min(u, v), max(u, v)});
    }
    graph<0, edge, 1> sp_dag(n);
    vector<int> ds(n + 1, lim<int>::max()), dt(n + 1, lim<int>::max());
    queue<int> q;
    q.push(1);
    ds[1] = 0;
    while(not q.empty()) {
        int u = q.front(); q.pop();
        for(int e : g[u]) {
            int v = g(e).v;
            if(ds[v] > ds[u] + 1) {
                ds[v] = ds[u] + 1;
                q.push(v);
                sp_dag.add_edge({min(u, v), max(u, v)});
            } else if(ds[v] == ds[u] + 1) {
                sp_dag.add_edge({min(u, v), max(u, v)});
            }
        }
    }
    q.push(n);
    dt[n] = 0;
    while(not q.empty()) {
        int u = q.front(); q.pop();
        for(int e : g[u]) {
            int v = g(e).v;
            if(dt[v] > dt[u] + 1) {
                dt[v] = dt[u] + 1;
                q.push(v);
            }
        }
    }
    auto [cut_edge, _2eccs] = find_2eccs(sp_dag);
    bool increase = false;
    for(int i = 0; i < m - 1; i++) {
        edge& sp_edge = sp_dag.edges[i << 1];
        increase |= cut_edge[i << 1] and 
            sp_edge.u != last_edge.u and 
            sp_edge.v != last_edge.v and
            (ds[sp_edge.u] + 1 + dt[sp_edge.v] == ds[n] or ds[sp_edge.v] + 1 + dt[sp_edge.u] == ds[n]);
    }
    cout << ds[n] + increase << endl;
    return 0;
}

Compilation message (stderr)

Aesthetic.cpp: In instantiation of 'std::pair<std::vector<int>, std::vector<std::vector<int> > > find_2eccs(graph<false, TEdge, Index>&) [with TEdge = edge; bool Index = true]':
Aesthetic.cpp:111:48:   required from here
Aesthetic.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int u = Index; u < g.adj.size(); u++) if(not vis[u]) {
      |                        ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 7
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27