oj.uz

Submission #31523

# Submission time Handle Problem Language Result Execution time Memory
31523 2017-08-29T07:25:41 Z user202729 Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 65100 KB 
//#define _GLIBCXX_DEBUG
//#define _GLIBCXX_DEBUG_PEDANTIC

#include <iostream>
#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::ios_base::sync_with_stdio(false);
//    std::cin.tie(nullptr);

    int nvertex, nedge;
    std::cin >> nvertex >> nedge;
    std::vector<std::list<edge>> adjlist (nvertex);
    for (int i = 0; i < nedge; ++i) {
        int u, v;
        std::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
    }

//    std::cout << "------------\n";

    std::vector<int> passedvertices;
    std::vector<char> passedp (nvertex, false);
    for (int vertex = 0; vertex < nvertex; ++vertex) {
//        std::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]) {
//                    std::cout << "Cycle :\n";
                    do {
                        std::cout << 1+passedvertices.back() << ' ';
                        passedp[passedvertices.back()] = false; passedvertices.pop_back();
                    } while (passedvertices.back() != nextvertex);
                    std::cout << 1+nextvertex << '\n';
                } else {
                    passedvertices.push_back(nextvertex);
                    passedp[nextvertex] = true;
                }
            }
        }
    }
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 292 KB Output is correct
4 Correct 9 ms 640 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 10 ms 768 KB Output is correct
7 Correct 18 ms 1792 KB Output is correct
8 Correct 9 ms 512 KB Output is correct
9 Correct 122 ms 10104 KB Output is correct
10 Correct 8 ms 640 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 111 ms 10156 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 10 ms 744 KB Output is correct
7 Correct 22 ms 1792 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 129 ms 10232 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 113 ms 10232 KB Output is correct
13 Correct 157 ms 13400 KB Output is correct
14 Correct 178 ms 12256 KB Output is correct
15 Correct 146 ms 11824 KB Output is correct
16 Correct 180 ms 13220 KB Output is correct
17 Correct 180 ms 11964 KB Output is correct
18 Correct 174 ms 12348 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 360 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 21 ms 1792 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 120 ms 10076 KB Output is correct
10 Correct 8 ms 640 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 112 ms 10232 KB Output is correct
13 Correct 157 ms 13296 KB Output is correct
14 Correct 170 ms 12372 KB Output is correct
15 Correct 142 ms 11852 KB Output is correct
16 Correct 163 ms 13272 KB Output is correct
17 Correct 192 ms 11972 KB Output is correct
18 Correct 175 ms 12384 KB Output is correct
19 Execution timed out 900 ms 65100 KB Time limit exceeded
20 Halted 0 ms 0 KB -