oj.uz

Submission #861252

# Submission time Handle Problem Language Result Execution time Memory
861252 2023-10-15T17:46:25 Z qwusha Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 109636 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef long double ld;
const ll inf = 1e9;
const ld eps = 1e-8;
vector<multiset<int>> g;
vector<vector<int>> ans;
vector<bool> used;
vector<int> cur;
set<int> stcur;
vector<int> res;

void dfs(int v) {
    if (stcur.find(v) != stcur.end()) {
        res.clear();
        while(cur.back() != v) {
            stcur.erase(cur.back());
            res.push_back(cur.back());
            cur.pop_back();
        }
        stcur.erase(cur.back());
        res.push_back(cur.back());
        cur.pop_back();
        ans.push_back(res);
    }
    if (v == 4) {
        int x = 1;
    }
    while (!g[v].empty()) {
        cur.push_back(v);
        stcur.insert(v);
        auto t = g[v].begin();
        int u = *t;
        g[v].erase(t);
        g[u].erase(g[u].find(v));
        dfs(u);
    }
}



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    used.resize(n);
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        g[v - 1].insert(u - 1);
        g[u - 1].insert(v - 1);
    }
    dfs(0);
    for (auto s : ans) {
        for (auto el : s) {
            cout << el + 1 << ' ';
        }
        cout << '\n';
    }
}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:30:13: warning: unused variable 'x' [-Wunused-variable]
   30 |         int x = 1;
      |             ^

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 3 ms 1116 KB Output is correct
7 Correct 11 ms 2908 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 80 ms 17100 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 83 ms 17400 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 3 ms 1216 KB Output is correct
7 Correct 15 ms 3016 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 75 ms 16928 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 2 ms 856 KB Output is correct
12 Correct 76 ms 17344 KB Output is correct
13 Correct 71 ms 22100 KB Output is correct
14 Correct 74 ms 20912 KB Output is correct
15 Correct 76 ms 20868 KB Output is correct
16 Correct 65 ms 22092 KB Output is correct
17 Correct 65 ms 20812 KB Output is correct
18 Correct 65 ms 16548 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 3 ms 1112 KB Output is correct
7 Correct 11 ms 2908 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 77 ms 17124 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 78 ms 17396 KB Output is correct
13 Correct 65 ms 22264 KB Output is correct
14 Correct 69 ms 21116 KB Output is correct
15 Correct 70 ms 20768 KB Output is correct
16 Correct 74 ms 22204 KB Output is correct
17 Correct 67 ms 20684 KB Output is correct
18 Correct 59 ms 16356 KB Output is correct
19 Execution timed out 555 ms 109636 KB Time limit exceeded
20 Halted 0 ms 0 KB -