Submission #983530

#	Time	Username	Problem	Language	Result	Execution time	Memory
983530		canadavid1	Senior Postmen (BOI14_postmen)	C++17	55 / 100	783 ms	88836 KiB

postmen

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


struct Node
{
    std::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-roads.data());
        nodes[i.b].roads.insert(&i-roads.data());
    }
    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 r = *nodes[out.back()].roads.begin();
            auto n = roads[r].a==out.back()?roads[r].b:roads[r].a;
            nodes[n].roads.erase(r);
            nodes[out.back()].roads.erase(r);
            out.push_back(n);
        }
    }
    std::vector<std::vector<int>> res;
    for(auto v : os)
    {
        std::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