Submission #983533

#	Time	Username	Problem	Language	Result	Execution time	Memory
983533		canadavid1	Senior Postmen (BOI14_postmen)	C++17	55 / 100	997 ms	135180 KiB

postmen

#include <iostream>
#include <vector>
#include <unordered_set>
struct Road
{
    int a,b;
    bool visit;
    bool full_visit;
};


struct Node
{
    std::unordered_set<int> roads;
};

int main()
{
    int N,M;
    std::cin >> N >> M;
    std::vector<Node> nodes(N+1);
    std::vector<Road> roads(M);
    for(auto& i : roads)
    {
        std::cin >> i.a >> i.b;
        nodes[i.a].roads.insert(i.b);
        nodes[i.b].roads.insert(i.a);
    }
    std::vector<std::vector<int>> os;
    int s = 1;
    while(s <= N)
    {
        auto& out = os.emplace_back();
        while(s <= N && nodes[s].roads.size()==0) s++;
        if(s>N) break;
        out.push_back(s);
        while(out.size()==1||out.back()!=out.front())
        {
            auto n = *nodes[out.back()].roads.begin();
            nodes[n].roads.erase(out.back());
            nodes[out.back()].roads.erase(n);
            out.push_back(n);
        }
    }
    std::vector<std::vector<int>> res;
    for(auto v : os)
    {
        std::unordered_set<int> seen;
        std::vector<int> out;
        for(auto i : v)
        {
            if(seen.count(i))
            {
                auto& w = res.emplace_back();
                w.push_back(i);
                while(out.back()!=i)
                {
                    w.push_back(out.back());
                    seen.erase(out.back());
                    out.pop_back();
                }

            }
            else 
            {
                seen.insert(i);
                out.push_back(i);
            }
        }
    }
    for(auto v : res)
    {
        for(auto i : v) std::cout << i << " ";
        std::cout << "\n";
    }


}

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