oj.uz

Submission #979153

# Submission time Handle Problem Language Result Execution time Memory
979153 2024-05-10T10:08:26 Z Sharky Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 118384 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 500005;
bool seen[N];
vector<pair<int, int>> adj[N];
vector<int> path;
vector<vector<int>> ans;
map<int, int> occ;

void dfs(int node) {
    while (!adj[node].empty()) {
        auto [son, idx] = adj[node].back();
        adj[node].pop_back();
        if (seen[idx]) continue;
        seen[idx] = true;
        dfs(son);
    }
    if (occ.count(node)) {
        int idx = occ[node];
        vector<int> tmp;
        while (path.size() >= idx + 1) {
            tmp.push_back(path.back());
            occ.erase(path.back());
            path.pop_back();
        }
        reverse(tmp.begin(), tmp.end());
        ans.push_back(tmp);
    }
    occ[node] = path.size();
    path.push_back(node);
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++) {
        while (!adj[i].empty()) dfs(i);
        if (path.size() > 1) ans.push_back(path); 
        path.clear();
    }
    for (auto& path : ans) {
        for (auto& e : path) cout << e << ' ';
        cout << '\n';
    }
}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:22:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |         while (path.size() >= idx + 1) {
      |                ~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 3 ms 12532 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 3 ms 12376 KB Output is correct
6 Correct 5 ms 12888 KB Output is correct
7 Correct 9 ms 14428 KB Output is correct
8 Correct 4 ms 12472 KB Output is correct
9 Correct 46 ms 26708 KB Output is correct
10 Correct 4 ms 12376 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 54 ms 27128 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12120 KB Output is correct
4 Correct 5 ms 12636 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 5 ms 12728 KB Output is correct
7 Correct 9 ms 14424 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 46 ms 26740 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 5 ms 12376 KB Output is correct
12 Correct 51 ms 27000 KB Output is correct
13 Correct 65 ms 33128 KB Output is correct
14 Correct 60 ms 25436 KB Output is correct
15 Correct 50 ms 29164 KB Output is correct
16 Correct 73 ms 33068 KB Output is correct
17 Correct 49 ms 19452 KB Output is correct
18 Correct 63 ms 27632 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12204 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 5 ms 12724 KB Output is correct
7 Correct 9 ms 14428 KB Output is correct
8 Correct 4 ms 12380 KB Output is correct
9 Correct 46 ms 26704 KB Output is correct
10 Correct 4 ms 12380 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 49 ms 27216 KB Output is correct
13 Correct 66 ms 33140 KB Output is correct
14 Correct 57 ms 25476 KB Output is correct
15 Correct 47 ms 29096 KB Output is correct
16 Correct 66 ms 32976 KB Output is correct
17 Correct 50 ms 19464 KB Output is correct
18 Correct 61 ms 27656 KB Output is correct
19 Execution timed out 513 ms 118384 KB Time limit exceeded
20 Halted 0 ms 0 KB -