제출 #31502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31502		user202729	어르신 집배원 (BOI14_postmen)	C++14	55 / 100	896 ms	91924 KiB

postmen

//#define _GLIBCXX_DEBUG
//#define _GLIBCXX_DEBUG_PEDANTIC

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <algorithm>

int main() {
    std::cin >> std::noskipws;
    std::string input;
    std::getline(std::cin, input, '$');
    std::stringstream cin (input);
    std::stringstream cout;
    // ----------------------

    int nvertex, nedge;
    cin >> nvertex >> nedge;
    std::vector<std::set<int>> adjlist (nvertex);
    for (int i = 0; i < nedge; ++i) {
        int u, v;
        cin >> u >> v;
        adjlist[--u].insert(--v);
        adjlist[v].insert(u);
    }

//    cout << "------------\n";

    std::vector<int> passedvertices;
    std::vector<char> passedp (nvertex, false);
    for (int vertex = 0; vertex < nvertex; ++vertex) {
//        cout << "vertex = " << vertex << '\n';
        while (!adjlist[vertex].empty()) {
            passedvertices.push_back(vertex);
            passedp[vertex] = true;
            while ((!passedvertices.empty()) && !adjlist[passedvertices.back()].empty()) {
                int nextvertex = *adjlist[passedvertices.back()].begin();
//                cout << "nextvertex = " << nextvertex << '\n';
                adjlist[passedvertices.back()].erase(adjlist[passedvertices.back()].begin());
                adjlist[nextvertex].erase(passedvertices.back());

                if (passedp[nextvertex]) {
//                    cout << "Cycle :\n";
                    do {
                        cout << 1+passedvertices.back() << ' ';
                        passedp[passedvertices.back()] = false; passedvertices.pop_back();
                    } while (passedvertices.back() != nextvertex);
                    cout << 1+nextvertex << '\n';
                } else {
                    passedvertices.push_back(nextvertex);
                    passedp[nextvertex] = true;
                }
            }
//            if ((!passedvertices.empty()) && adjlist[passedvertices.back()].empty()) {
//                cout << "error\n";
//                for (int i : passedvertices) cout << i << ' ';
//                cout << '\n';
//                while (true);
//            }
//            else cout << "****\n";
        }
    }

    // ----------------------
    std::cout << cout.str();

}

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45