Submission #727277

#	Time	Username	Problem	Language	Result	Execution time	Memory
727277		Tigerpants	Senior Postmen (BOI14_postmen)	C++17	55 / 100	507 ms	74432 KiB

postmen

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <unordered_set>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef set<ll> sll;
typedef vector<vll> vvll;
typedef vector<sll> vsll;
typedef vector<bool> vb;
typedef unordered_set<ll> usll;
typedef vector<usll> vusll;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define sz(a) a.size()

ll N, M;
vvll g;

vll S;
vb onS;

vb vis;
vll e[2];

ll getU(ll i, ll v) {
    return (v == e[0][i]) ? e[1][i] : e[0][i];
}

bool DFS(ll cur) {
    if (onS[cur]) {
        // found axon
        cout << cur + 1 << " ";
        onS[cur] = false;
        return true;
    } else {
        onS[cur] = true;
        S.pb(cur);
        while (!g[cur].empty()) {
            ll edge = g[cur].back();
            g[cur].pop_back();
            if (vis[edge]) {
                continue;
            }
            ll nxt = getU(edge, cur);

            vis[edge] = true;
            
            if (DFS(nxt)) {
                if (onS[cur]) {
                    cout << cur + 1 << " ";
                    onS[cur] = false;
                    S.pop_back();
                    return true;
                } else {
                    onS[cur] = true;
                    cout << "\n";
                }
            }
        }
        S.pop_back();
        return false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    g.resize(N);
    e[0].resize(M);
    e[1].resize(M);
    ll tmpa, tmpb;
    rep(i, 0, M) {
        cin >> e[0][i] >> e[1][i];
        e[0][i]--; e[1][i]--;
        g[e[0][i]].pb(i);
        g[e[1][i]].pb(i);
    }

    onS.resize(N, false);
    vis.resize(M, false);

    rep(i, 0, N) {
        DFS(i);
    }

    return 0;
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:83:8: warning: unused variable 'tmpa' [-Wunused-variable]
   83 |     ll tmpa, tmpb;
      |        ^~~~
postmen.cpp:83:14: warning: unused variable 'tmpb' [-Wunused-variable]
   83 |     ll tmpa, tmpb;
      |              ^~~~

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