oj.uz

Submission #703586

# Submission time Handle Problem Language Result Execution time Memory
703586 2023-02-27T18:05:01 Z sheldon Senior Postmen (BOI14_postmen) C++17
100 / 100
 403 ms 50096 KB 
#include <bits/stdc++.h>

using namespace std;

const int nax = 5e5 + 5;

vector<pair<int, int>> edges[nax];
int deg[nax], where[nax];
bool used[nax];

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        ++deg[u], ++deg[v];
        edges[u].push_back({v, i});
        edges[v].push_back({u, i});
    }
    vector<int> st = {1}, ans;
    int at = 1;
    while (!st.empty()) {
        if (deg[at]) {
            st.push_back(at);
            while (used[edges[at].back().second]) {
                edges[at].pop_back();
            }
            --deg[at];
            used[edges[at].back().second] = 1;
            at = edges[at].back().first;
            --deg[at];
        } else {
            ans.push_back(at);
            at = st.back();
            st.pop_back();
        }
    }
    vector<pair<int, int>> stt;
    for (int i = 0; i < nax; ++i) {
        where[i] = -1;
    }
    for (int i = 0; i < ans.size(); ++i) {
        stt.push_back({ans[i], i});
        if (where[ans[i]] != -1) {
            int x = where[ans[i]];
            while (stt.back().second > x) {
                where[stt.back().first] = -1;
                cout << stt.back().first << ' ';
                stt.pop_back();
            }
            where[ans[i]] = stt.back().second;
            cout << '\n';
        } else {
            where[ans[i]] = i;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message

postmen.cpp: In function 'void solve()':
postmen.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < ans.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14028 KB Output is correct
2 Correct 8 ms 13992 KB Output is correct
3 Correct 8 ms 13988 KB Output is correct
4 Correct 8 ms 14128 KB Output is correct
5 Correct 7 ms 14060 KB Output is correct
6 Correct 8 ms 14260 KB Output is correct
7 Correct 12 ms 14768 KB Output is correct
8 Correct 8 ms 14128 KB Output is correct
9 Correct 34 ms 18088 KB Output is correct
10 Correct 10 ms 14164 KB Output is correct
11 Correct 9 ms 14132 KB Output is correct
12 Correct 35 ms 18568 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13908 KB Output is correct
2 Correct 7 ms 14036 KB Output is correct
3 Correct 7 ms 14036 KB Output is correct
4 Correct 8 ms 14096 KB Output is correct
5 Correct 8 ms 14036 KB Output is correct
6 Correct 8 ms 14260 KB Output is correct
7 Correct 12 ms 14804 KB Output is correct
8 Correct 8 ms 14132 KB Output is correct
9 Correct 32 ms 18096 KB Output is correct
10 Correct 8 ms 14132 KB Output is correct
11 Correct 7 ms 14192 KB Output is correct
12 Correct 36 ms 18528 KB Output is correct
13 Correct 52 ms 21096 KB Output is correct
14 Correct 48 ms 20164 KB Output is correct
15 Correct 47 ms 19632 KB Output is correct
16 Correct 52 ms 21064 KB Output is correct
17 Correct 61 ms 19376 KB Output is correct
18 Correct 58 ms 20116 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13908 KB Output is correct
2 Correct 7 ms 13944 KB Output is correct
3 Correct 8 ms 14040 KB Output is correct
4 Correct 11 ms 14128 KB Output is correct
5 Correct 8 ms 14036 KB Output is correct
6 Correct 9 ms 14164 KB Output is correct
7 Correct 10 ms 14804 KB Output is correct
8 Correct 7 ms 14164 KB Output is correct
9 Correct 32 ms 18096 KB Output is correct
10 Correct 8 ms 14164 KB Output is correct
11 Correct 9 ms 14236 KB Output is correct
12 Correct 37 ms 18612 KB Output is correct
13 Correct 49 ms 21068 KB Output is correct
14 Correct 50 ms 20044 KB Output is correct
15 Correct 51 ms 19620 KB Output is correct
16 Correct 49 ms 21040 KB Output is correct
17 Correct 48 ms 19348 KB Output is correct
18 Correct 56 ms 20212 KB Output is correct
19 Correct 356 ms 50032 KB Output is correct
20 Correct 339 ms 45368 KB Output is correct
21 Correct 286 ms 42548 KB Output is correct
22 Correct 364 ms 50096 KB Output is correct
23 Correct 137 ms 33096 KB Output is correct
24 Correct 403 ms 41688 KB Output is correct
25 Correct 348 ms 45492 KB Output is correct