Submission #31527

#	Time	Username	Problem	Language	Result	Execution time	Memory
31527		user202729	Senior Postmen (BOI14_postmen)	C++14	55 / 100	844 ms	80196 KiB

postmen

//#define _GLIBCXX_DEBUG
//#define _GLIBCXX_DEBUG_PEDANTIC

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

struct edge {
    int vertex;
    std::list<edge>::iterator opposite;
    edge(int vertex, std::list<edge>::iterator opposite) : vertex(vertex), opposite(opposite) {};
    edge(int vertex) : vertex(vertex) {};
};

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::list<edge>> adjlist (nvertex);
    for (int i = 0; i < nedge; ++i) {
        int u, v;
        cin >> u >> v;
        adjlist[--u].emplace_front(--v);
        adjlist[v].emplace_front(u);
        adjlist[u].front().opposite = adjlist[v].begin(); // begin = iterator of front
        adjlist[v].front().opposite = adjlist[u].begin(); // begin = iterator of front
    }

//    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()) {
                edge e = adjlist[passedvertices.back()].back();
                int nextvertex = e.vertex;
                adjlist[nextvertex].erase(e.opposite);
                adjlist[passedvertices.back()].pop_back(); // erase (e)

                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;
                }
            }
        }
    }

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

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