제출 #31497

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

postmen

//#define _GLIBCXX_DEBUG
//#define _GLIBCXX_DEBUG_PEDANTIC

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

int main() {
//    std::ios_base::sync_with_stdio(false);
//    std::cin.tie(nullptr);

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

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

    std::vector<int> passedvertices;
    std::vector<char> passedp (nvertex, false);
    for (int vertex = 0; vertex < nvertex; ++vertex) {
//        std::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();
//                std::cout << "nextvertex = " << nextvertex << '\n';
                adjlist[passedvertices.back()].erase(adjlist[passedvertices.back()].begin());
                adjlist[nextvertex].erase(passedvertices.back());

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

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