oj.uz

Submission #31527

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

#include <iostream>
#include <sstream>
#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::cin >> std::noskipws;
    std::string input;
    std::getline(std::cin, input, '$');
    std::stringstream cin (input);
    std::stringstream cout;
    // ----------------------

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

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

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

    // ----------------------
    std::cout << cout.str();
}

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 5 ms 256 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 8 ms 768 KB Output is correct
7 Correct 17 ms 1920 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 90 ms 11568 KB Output is correct
10 Correct 8 ms 768 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 97 ms 12076 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 8 ms 256 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 15 ms 1920 KB Output is correct
8 Correct 7 ms 616 KB Output is correct
9 Correct 97 ms 11580 KB Output is correct
10 Correct 8 ms 768 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 99 ms 12080 KB Output is correct
13 Correct 150 ms 15952 KB Output is correct
14 Correct 153 ms 16220 KB Output is correct
15 Correct 136 ms 14576 KB Output is correct
16 Correct 150 ms 16028 KB Output is correct
17 Correct 163 ms 15664 KB Output is correct
18 Correct 158 ms 16028 KB Output is correct

Subtask #3
0 / 45.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 768 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 17 ms 1972 KB Output is correct
8 Correct 6 ms 640 KB Output is correct
9 Correct 91 ms 11532 KB Output is correct
10 Correct 7 ms 768 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 98 ms 12088 KB Output is correct
13 Correct 155 ms 16080 KB Output is correct
14 Correct 158 ms 16084 KB Output is correct
15 Correct 120 ms 14548 KB Output is correct
16 Correct 150 ms 15976 KB Output is correct
17 Correct 156 ms 15700 KB Output is correct
18 Correct 155 ms 15952 KB Output is correct
19 Execution timed out 844 ms 80196 KB Time limit exceeded
20 Halted 0 ms 0 KB -