oj.uz

Submission #727261

# Submission time Handle Problem Language Result Execution time Memory
727261 2023-04-20T10:28:43 Z Tigerpants Senior Postmen (BOI14_postmen) C++17
0 / 100
 500 ms 9292 KB 
#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;
vusll g;

void remove_edge(ll a, ll b) {
    g[a].erase(b);
    g[b].erase(a);
}

vll S;
vb onS;

vvll paths;

bool DFS(ll cur) {
    if (onS[cur]) {
        // found axon
        paths.pb(vll());
        paths.back().pb(cur);
        onS[cur] = false;
        return true;
    } else {
        onS[cur] = true;
        S.pb(cur);
        vll neighborhood(g[cur].begin(), g[cur].end());
        for (vll::iterator nxt = neighborhood.begin(); nxt != neighborhood.end(); nxt++) {
            if (g[cur].count(*nxt) == 0) continue;
            remove_edge(cur, *nxt);
            if (DFS(*nxt)) {
                if (onS[cur]) {
                    paths.back().pb(cur);
                    onS[cur] = false;
                    S.pop_back();
                    return true;
                } else {
                    onS[cur] = true;
                }
            }
        }
        S.pop_back();
        return false;
    }
}

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

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

    onS.resize(N, false);

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

    for (vvll::iterator path = paths.begin(); path != paths.end(); path++) {
        for (vll::iterator itr = path->begin(); itr != path->end(); itr++) {
            cout << (*itr) + 1 << " ";
        }
        cout << "\n";
    }
    cout << flush;

    return 0;
}

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 25 ms 1868 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Execution timed out 699 ms 9240 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 780 KB Output is correct
7 Correct 23 ms 1876 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Execution timed out 678 ms 9248 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 26 ms 1932 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Execution timed out 737 ms 9292 KB Time limit exceeded
10 Halted 0 ms 0 KB -