oj.uz

Submission #983533

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 344 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 11 ms 1984 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 72 ms 10148 KB Output is correct
10 Correct 3 ms 856 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 80 ms 10304 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 11 ms 1884 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 72 ms 9924 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 78 ms 10460 KB Output is correct
13 Correct 145 ms 27784 KB Output is correct
14 Correct 141 ms 22072 KB Output is correct
15 Correct 127 ms 22488 KB Output is correct
16 Correct 139 ms 27772 KB Output is correct
17 Correct 135 ms 20924 KB Output is correct
18 Correct 127 ms 22516 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 1012 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 11 ms 1996 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 71 ms 10156 KB Output is correct
10 Correct 3 ms 856 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 80 ms 10328 KB Output is correct
13 Correct 146 ms 27764 KB Output is correct
14 Correct 141 ms 21780 KB Output is correct
15 Correct 130 ms 22356 KB Output is correct
16 Correct 146 ms 27780 KB Output is correct
17 Correct 126 ms 21004 KB Output is correct
18 Correct 139 ms 22512 KB Output is correct
19 Execution timed out 997 ms 135180 KB Time limit exceeded
20 Halted 0 ms 0 KB -