oj.uz

Submission #980669

# Submission time Handle Problem Language Result Execution time Memory
980669 2024-05-12T09:59:19 Z Zicrus Senior Postmen (BOI14_postmen) C++17
55 / 100
 133 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, u, v;
vector<queue<pair<int, int>>> adj;
vector<int> res;

vector<bool> sus;

void euler(int s) {
    while (!adj[s].empty()) {
        int e = adj[s].front().first;
        int i = adj[s].front().second;
        adj[s].pop();
        if (!sus[i]) { sus[i] = true; euler(e); }
        sus[i] = true;
    }
    res.push_back(s);
}

int main() {
    cin >> n >> m;
    adj.resize(n);
    sus.resize(m);
    vector<int> deg(n);
    int g = 0;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        adj[u-1].push({v-1, g});
        adj[v-1].push({u-1, g++});
    }

    euler(0);
    reverse(res.begin(), res.end());
    vector<int> vst(n, -1);
    vector<int> nxt(n, -1);
    for (int i = 0; i < res.size(); i++) {
        int node = res[i];
        if (vst[node] == -1) {
            vst[node] = i;
            nxt[node] = res[i+1];
        }
        else {
            int nd = res[vst[node]];
            do {
                cout << nd+1 << ' ';
                vst[nd] = -1;
                nd = nxt[nd];
            } while (nd != node);
            cout << '\n';
            nxt[node] = res[i+1];
            vst[node] = i;
        }
    }
}

Compilation message

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

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 1880 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 9 ms 1884 KB Output is correct
8 Correct 2 ms 1884 KB Output is correct
9 Correct 47 ms 10580 KB Output is correct
10 Correct 2 ms 1880 KB Output is correct
11 Correct 2 ms 1884 KB Output is correct
12 Correct 53 ms 11472 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 1884 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 7 ms 1880 KB Output is correct
8 Correct 2 ms 2136 KB Output is correct
9 Correct 47 ms 10576 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 2 ms 1884 KB Output is correct
12 Correct 52 ms 11476 KB Output is correct
13 Correct 133 ms 77892 KB Output is correct
14 Correct 101 ms 56792 KB Output is correct
15 Correct 105 ms 54864 KB Output is correct
16 Correct 129 ms 77744 KB Output is correct
17 Correct 111 ms 48076 KB Output is correct
18 Correct 104 ms 58776 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 7 ms 1884 KB Output is correct
8 Correct 2 ms 1880 KB Output is correct
9 Correct 49 ms 10668 KB Output is correct
10 Correct 2 ms 1884 KB Output is correct
11 Correct 2 ms 1884 KB Output is correct
12 Correct 53 ms 11472 KB Output is correct
13 Correct 117 ms 77776 KB Output is correct
14 Correct 102 ms 57228 KB Output is correct
15 Correct 100 ms 54928 KB Output is correct
16 Correct 112 ms 77748 KB Output is correct
17 Correct 112 ms 48020 KB Output is correct
18 Correct 117 ms 58788 KB Output is correct
19 Runtime error 123 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -