Submission #820053

#	Time	Username	Problem	Language	Result	Execution time	Memory
820053		DylanSmith	Senior Postmen (BOI14_postmen)	C++17	100 / 100	339 ms	63508 KiB

postmen

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)
 
mt19937 rng;

class Hierholzer { public:
    struct Edge { int to, rev; bool vis; };

    vector<vector<Edge>> adj;
    bool dir;
    int N, M;
    void addEdge(int u, int v) {
        int pos1 = sz(adj[u]), pos2 = sz(adj[v]);
        if (u == v) pos2++;
        adj[u].pb({v, pos2, 0});
        if (!dir) adj[v].pb({u, pos1, 0});
        M++;
    }

    vector<int> adjPos;
    void rec(vector<int> &res, int u) {
        while (adjPos[u] < sz(adj[u]) && adj[u][adjPos[u]].vis) adjPos[u]++;
        if (adjPos[u] < sz(adj[u])) {
            Edge e = adj[u][adjPos[u]];
            if (!dir) adj[e.to][e.rev].vis = true;
            adj[u][adjPos[u]++].vis = true;
            rec(res, e.to);
            rec(res, u);
        } else res.pb(u);
    }

    bool possible(int start, int end) {
        if (dir) {
            vector<int> inCnt(N, 0), outCnt(N, 0);
            for (int u = 0; u < N; u++) outCnt[u] = sz(adj[u]);
            for (int u = 0; u < N; u++) for (Edge e : adj[u]) inCnt[e.to]++;
            if (start == end && inCnt[start] != outCnt[start]) return false;
            if (start != end && inCnt[start] + 1 != outCnt[start]) return false;
            if (start != end && inCnt[end] != outCnt[end] + 1) return false;
            for (int i = 0; i < sz(adj); i++)
                if (i != start && i != end && inCnt[i] != outCnt[i]) return false;
        } else {
            if (start == end && sz(adj[start]) % 2 == 1) return false;
            if (start != end && (sz(adj[start]) + sz(adj[end])) % 2 == 1) return false;
            for (int i = 0; i < sz(adj); i++)
                if (i != start && i != end && sz(adj[i]) % 2 == 1) return false;
        }
        return true;
    }

    bool path(vector<int> &res, int start, int end) {
        if (!possible(start, end)) return false;
        adjPos = vector<int>(sz(adj), 0);
        rec(res, start);
        reverse(res.begin(), res.end());
        return sz(res) == M + 1;
    }

    Hierholzer(int _N, bool directed) {
        N = _N; M = 0;
        adj = vector<vector<Edge>>(N);
        dir = directed;
    }
};

void solve() {
    int N, M; cin >> N >> M;
    Hierholzer h(N, false);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v; u--; v--;
        h.addEdge(u, v);
    }
    vector<int> path;
    h.path(path, 0, 0);
    vector<int> prev(N, -1);
    vector<int> nxt, pos;
    stack<int> st;
    for (int i = 0; i < sz(path); i++) {
        if (prev[path[i]] >= 0) {
            vector<int> curPath;
            int j = pos[prev[path[i]]];
            while (!st.empty() && st.top() >= j) {
                curPath.pb(path[st.top()]);
                prev[path[st.top()]] = nxt[prev[path[st.top()]]];
                st.pop();
            }
            for (int i = 0; i < sz(curPath); i++) {
                cout << (curPath[i] + 1) << (i == sz(curPath) - 1 ? "\n" : " ");
            }
        }
        pos.pb(i);
        nxt.pb(prev[path[i]]);
        prev[path[i]] = sz(nxt) - 1;
        st.push(i);
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
 
    solve();
 
    return 0;
}

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 45 / 45