oj.uz

Submission #861255

# Submission time Handle Problem Language Result Execution time Memory
861255 2023-10-15T17:49:21 Z qwusha Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 109532 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
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);
    cout.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:4: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    4 | #pragma gcc optimize("Ofast")
      | 
postmen.cpp: In function 'void dfs(int)':
postmen.cpp:33:13: warning: unused variable 'x' [-Wunused-variable]
   33 |         int x = 1;
      |             ^

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 860 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct
7 Correct 11 ms 2904 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 106 ms 16936 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 85 ms 17276 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 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 13 ms 2908 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 81 ms 17048 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 85 ms 17484 KB Output is correct
13 Correct 65 ms 22308 KB Output is correct
14 Correct 62 ms 21008 KB Output is correct
15 Correct 78 ms 20684 KB Output is correct
16 Correct 64 ms 22092 KB Output is correct
17 Correct 65 ms 20684 KB Output is correct
18 Correct 75 ms 16516 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 0 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 81 ms 16968 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 89 ms 17344 KB Output is correct
13 Correct 70 ms 22308 KB Output is correct
14 Correct 67 ms 21036 KB Output is correct
15 Correct 69 ms 20764 KB Output is correct
16 Correct 85 ms 22212 KB Output is correct
17 Correct 66 ms 20780 KB Output is correct
18 Correct 58 ms 16352 KB Output is correct
19 Execution timed out 548 ms 109532 KB Time limit exceeded
20 Halted 0 ms 0 KB -