Submission #861090

#	Time	Username	Problem	Language	Result	Execution time	Memory
861090		Ellinor	Senior Postmen (BOI14_postmen)	C++14	100 / 100	334 ms	85020 KiB

postmen

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define rrep(i, a, b) for (int i = (a) - 1; i >= int(b); i--)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1000000000;
ll mod = 1e9 + 7;

#define int ll
#define float double

//

int N, M;
vector<vector<pii>> graph;
vector<bool> visited_node, visited_edge;

vector<vector<int>> tours;
vector<int> tour;

int dfs(int node) {
    // cerr << "enter " << node + 1 << "\n";
    visited_node[node] = true;

    int ret = -1;
    while (true) {
        rrep(i, graph[node].size(), 0) {
            // cerr << "edge " << graph[node][i].first << " " << graph[node][i].second + 1 << "\n";
            if (visited_edge[graph[node][i].first]) graph[node].pop_back();
            else if (visited_node[graph[node][i].second]) {
                visited_edge[graph[node][i].first] = true;
                ret = graph[node][i].second;
                graph[node].pop_back();
                break;
            }
            else {
                visited_edge[graph[node][i].first] = true;
                int n = graph[node][i].second;
                graph[node].pop_back();
                ret = dfs(n);
                break;
            }
        }
        if (ret == node) {
            tour.pb(node);
            tours.pb(tour);
            tour.clear(); //
            ret = -1;
        }
        else if (ret != -1) {
            tour.pb(node);
            break;
        }
        if (graph[node].size() == 0) return -2;
    }

    //
    visited_node[node] = false;
    // cerr << "leaving " << node + 1 << "\n";
    return ret;
}

int32_t main()
{
    fast();
    cin >> N >> M;
    graph.assign(N, {});
    int a, b;
    int e = 0;
    rep(i,0,M) {
        cin >> a >> b;
        a--; b--;
        graph[a].pb({e, b});
        graph[b].pb({e, a});
        e++;
    }
    // assert even
    visited_node.assign(N, false);
    visited_edge.assign(M, false);

    rep(i,0,N) {
        while (graph[i].size() > 0) {
            dfs(i);
        }
    }

    rep(i,0,tours.size()) {
        rep(j,0,tours[i].size()) {
            cout << tours[i][j] + 1 << " ";
        }
        cout << "\n";
    }
}

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