oj.uz

답안 #31497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31497 2017-08-29T06:58:17 Z user202729 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 76824 KB 
//#define _GLIBCXX_DEBUG
//#define _GLIBCXX_DEBUG_PEDANTIC

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

int main() {
//    std::ios_base::sync_with_stdio(false);
//    std::cin.tie(nullptr);

    int nvertex, nedge;
    std::cin >> nvertex >> nedge;
    std::vector<std::set<int>> adjlist (nvertex);
    for (int i = 0; i < nedge; ++i) {
        int u, v;
        std::cin >> u >> v;
        adjlist[--u].insert(--v);
        adjlist[v].insert(u);
    }

//    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()) {
                int nextvertex = *adjlist[passedvertices.back()].begin();
//                std::cout << "nextvertex = " << nextvertex << '\n';
                adjlist[passedvertices.back()].erase(adjlist[passedvertices.back()].begin());
                adjlist[nextvertex].erase(passedvertices.back());

                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;
                }
            }
//            if ((!passedvertices.empty()) && adjlist[passedvertices.back()].empty()) {
//                std::cout << "error\n";
//                for (int i : passedvertices) std::cout << i << ' ';
//                std::cout << '\n';
//                while (true);
//            }
//            else std::cout << "****\n";
        }
    }
}

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 300 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 8 ms 640 KB Output is correct
5 Correct 7 ms 488 KB Output is correct
6 Correct 10 ms 768 KB Output is correct
7 Correct 26 ms 1792 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 193 ms 10080 KB Output is correct
10 Correct 8 ms 640 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 221 ms 10232 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 11 ms 640 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 11 ms 768 KB Output is correct
7 Correct 29 ms 1792 KB Output is correct
8 Correct 9 ms 640 KB Output is correct
9 Correct 201 ms 10080 KB Output is correct
10 Correct 8 ms 768 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 200 ms 10308 KB Output is correct
13 Correct 165 ms 15672 KB Output is correct
14 Correct 185 ms 14176 KB Output is correct
15 Correct 191 ms 13408 KB Output is correct
16 Correct 171 ms 15648 KB Output is correct
17 Correct 198 ms 13440 KB Output is correct
18 Correct 183 ms 14192 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 9 ms 768 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 23 ms 1792 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 197 ms 10080 KB Output is correct
10 Correct 9 ms 640 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 198 ms 10232 KB Output is correct
13 Correct 162 ms 15600 KB Output is correct
14 Correct 177 ms 14200 KB Output is correct
15 Correct 174 ms 13428 KB Output is correct
16 Correct 161 ms 15576 KB Output is correct
17 Correct 194 ms 13496 KB Output is correct
18 Correct 188 ms 14300 KB Output is correct
19 Execution timed out 891 ms 76824 KB Time limit exceeded
20 Halted 0 ms 0 KB -