oj.uz

Submission #983530

# Submission time Handle Problem Language Result Execution time Memory
983530 2024-05-15T15:51:31 Z canadavid1 Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 88836 KB 
#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.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 13 ms 2140 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 109 ms 11968 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 115 ms 12240 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 14 ms 1976 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 106 ms 11860 KB Output is correct
10 Correct 3 ms 856 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 113 ms 12252 KB Output is correct
13 Correct 102 ms 17868 KB Output is correct
14 Correct 91 ms 17200 KB Output is correct
15 Correct 111 ms 18060 KB Output is correct
16 Correct 105 ms 17868 KB Output is correct
17 Correct 124 ms 17148 KB Output is correct
18 Correct 94 ms 17736 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 5 ms 932 KB Output is correct
7 Correct 14 ms 2140 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 108 ms 11940 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 856 KB Output is correct
12 Correct 115 ms 12476 KB Output is correct
13 Correct 103 ms 17864 KB Output is correct
14 Correct 105 ms 17084 KB Output is correct
15 Correct 99 ms 17860 KB Output is correct
16 Correct 99 ms 17868 KB Output is correct
17 Correct 148 ms 17172 KB Output is correct
18 Correct 95 ms 17788 KB Output is correct
19 Execution timed out 783 ms 88836 KB Time limit exceeded
20 Halted 0 ms 0 KB -