oj.uz

답안 #928599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
928599 2024-02-16T17:51:01 Z tomb 어르신 집배원 (BOI14_postmen) C++17
55 / 100
 500 ms 130880 KB 
#include<bits/stdc++.h>
using namespace std;
#define MAXN (int) 5e5
#define ll long long
#define pb push_back
#define eb emplace_back
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define vpli vector<pli>
#define vpil vector<pil>
#define vpll vector<pll>
#define pii pair<int, int>
#define vpii vector<pii>
#define vi vector<int>
#define vvi vector<vi>

unordered_set<int> adj[MAXN];

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        u--,v--;
        adj[u].insert(v);
        adj[v].insert(u);
    }



    stack<int> st;
    st.push(0);
    vvi paths;
    // vi path;
    vi vis;
    unordered_map<int, int> vis_idx;
    while (st.size()){
        int u = st.top();

        // if (vis.size() && u == vis.front())
        // {
        //     // reverse(vis.begin(), vis.end());
        //     paths.pb(vis);
        //     vis.clear();
        // }
        if (vis_idx.count(u) && vis_idx[u] != -1){
            vi path;
            while (vis.size() && vis.back() != u){
                path.pb(vis.back());
                vis_idx[vis.back()] = -1;
                vis.pop_back();
            }
            path.pb(u);
            reverse(path.begin(), path.end());
            paths.pb(path);
            if (vis.size()) vis.pop_back();
        }
        

        if (adj[u].size()){
            vis.pb(u);
            vis_idx[u] = vis.size() - 1;
            auto v = adj[u].begin();
            st.push(*v);
            adj[*v].erase(u);
            adj[u].erase(*v);
        }
        else {
            st.pop();
            // path.pb(u);
        }
    }
    // cout << "ans: " << endl;
    for (auto p : paths){
        if (p.size() == 1) continue;
        for (int i : p) cout << i + 1 << " ";
        cout << endl;
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 27736 KB Output is correct
2 Correct 7 ms 27740 KB Output is correct
3 Correct 7 ms 27740 KB Output is correct
4 Correct 10 ms 28252 KB Output is correct
5 Correct 8 ms 27736 KB Output is correct
6 Correct 12 ms 28252 KB Output is correct
7 Correct 18 ms 29276 KB Output is correct
8 Correct 9 ms 27996 KB Output is correct
9 Correct 85 ms 36516 KB Output is correct
10 Correct 10 ms 28252 KB Output is correct
11 Correct 10 ms 28252 KB Output is correct
12 Correct 101 ms 36796 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 27740 KB Output is correct
2 Correct 7 ms 27740 KB Output is correct
3 Correct 7 ms 27740 KB Output is correct
4 Correct 10 ms 28252 KB Output is correct
5 Correct 8 ms 27740 KB Output is correct
6 Correct 12 ms 28248 KB Output is correct
7 Correct 19 ms 29188 KB Output is correct
8 Correct 8 ms 27996 KB Output is correct
9 Correct 81 ms 36568 KB Output is correct
10 Correct 10 ms 28252 KB Output is correct
11 Correct 10 ms 28252 KB Output is correct
12 Correct 94 ms 37160 KB Output is correct
13 Correct 140 ms 48620 KB Output is correct
14 Correct 166 ms 44568 KB Output is correct
15 Correct 187 ms 47208 KB Output is correct
16 Correct 153 ms 48476 KB Output is correct
17 Correct 169 ms 44160 KB Output is correct
18 Correct 201 ms 44768 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 27736 KB Output is correct
2 Correct 7 ms 27740 KB Output is correct
3 Correct 7 ms 27780 KB Output is correct
4 Correct 10 ms 28248 KB Output is correct
5 Correct 8 ms 27736 KB Output is correct
6 Correct 10 ms 28252 KB Output is correct
7 Correct 18 ms 29276 KB Output is correct
8 Correct 9 ms 28252 KB Output is correct
9 Correct 81 ms 36636 KB Output is correct
10 Correct 11 ms 28504 KB Output is correct
11 Correct 11 ms 28252 KB Output is correct
12 Correct 92 ms 36856 KB Output is correct
13 Correct 140 ms 48704 KB Output is correct
14 Correct 155 ms 44720 KB Output is correct
15 Correct 176 ms 46808 KB Output is correct
16 Correct 131 ms 48700 KB Output is correct
17 Correct 187 ms 44324 KB Output is correct
18 Correct 159 ms 44712 KB Output is correct
19 Execution timed out 1014 ms 130880 KB Time limit exceeded
20 Halted 0 ms 0 KB -