oj.uz

Submission #727280

# Submission time Handle Problem Language Result Execution time Memory
727280 2023-04-20T11:07:09 Z Tigerpants Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 85084 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;
vvll g;
vll pr;

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 (pr[cur] >= 0) {
            ll edge = g[cur][pr[cur]];
            pr[cur]--;
            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);
    pr.resize(N, -1);
    e[0].resize(M);
    e[1].resize(M);
    rep(i, 0, M) {
        cin >> e[0][i] >> e[1][i];
        e[0][i]--; e[1][i]--;
        g[e[0][i]].pb(i);
        pr[e[0][i]]++;
        g[e[1][i]].pb(i);
        pr[e[1][i]]++;
    }

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

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

    return 0;
}

Subtask #1
38.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 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 5 ms 980 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 27 ms 4328 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 35 ms 4696 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 5 ms 1084 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 34 ms 4344 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 31 ms 4616 KB Output is correct
13 Correct 58 ms 15924 KB Output is correct
14 Correct 59 ms 7712 KB Output is correct
15 Correct 43 ms 7064 KB Output is correct
16 Correct 57 ms 15816 KB Output is correct
17 Correct 57 ms 7288 KB Output is correct
18 Correct 50 ms 9612 KB Output is correct

Subtask #3
0 / 45.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 2 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 5 ms 980 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 28 ms 4212 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 31 ms 4704 KB Output is correct
13 Correct 57 ms 15880 KB Output is correct
14 Correct 56 ms 7688 KB Output is correct
15 Correct 56 ms 7044 KB Output is correct
16 Correct 68 ms 15944 KB Output is correct
17 Correct 63 ms 7320 KB Output is correct
18 Correct 65 ms 9548 KB Output is correct
19 Correct 491 ms 78288 KB Output is correct
20 Correct 448 ms 44364 KB Output is correct
21 Correct 415 ms 39640 KB Output is correct
22 Correct 482 ms 85084 KB Output is correct
23 Correct 145 ms 22764 KB Output is correct
24 Execution timed out 521 ms 41996 KB Time limit exceeded
25 Halted 0 ms 0 KB -