oj.uz

Submission #547281

# Submission time Handle Problem Language Result Execution time Memory
547281 2022-04-10T08:41:56 Z Jomnoi Senior Postmen (BOI14_postmen) C++17
38 / 100
 500 ms 21592 KB 
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
 
const int MAX_N = 5e5 + 10;
 
vector <pair <int, int>> graph[MAX_N];
vector <int> order;
bool used[MAX_N], is_print[MAX_N];
int visited[MAX_N];
 
void dfs(int u) {
    while(!graph[u].empty()) {
        auto [v, i] = graph[u].back();
        graph[u].pop_back();

        if(used[i] == false) {
            used[i] = true;
            dfs(v);
        }
    }
    order.push_back(u);
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(v, i);
        graph[v].emplace_back(u, i);
    }

    dfs(1);

    for(int i = 0; i < order.size(); i++) {
        if(visited[order[i]] != 0) {
            int j = i;
            while(j >= visited[order[i]]) {
                if(is_print[j] == false) {
                    cout << order[j] << ' ';
                    if(order[i] != order[j]) {
                        visited[order[j]] = 0;
                    }
                    is_print[j] = true;
                }
                j--;
            }
            cout << '\n';
        }
        else {
            visited[order[i]] = i + 1;
        }
    }
    return 0;
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < order.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 11 ms 12352 KB Output is correct
5 Correct 8 ms 12192 KB Output is correct
6 Correct 7 ms 12456 KB Output is correct
7 Correct 11 ms 13396 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 44 ms 19836 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 9 ms 12244 KB Output is correct
12 Correct 41 ms 20092 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 12416 KB Output is correct
7 Correct 11 ms 13396 KB Output is correct
8 Correct 8 ms 12244 KB Output is correct
9 Correct 45 ms 19756 KB Output is correct
10 Correct 8 ms 12168 KB Output is correct
11 Correct 7 ms 12260 KB Output is correct
12 Correct 46 ms 20168 KB Output is correct
13 Correct 54 ms 21576 KB Output is correct
14 Execution timed out 968 ms 18896 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12000 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 9 ms 12244 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 8 ms 12492 KB Output is correct
7 Correct 13 ms 13396 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 43 ms 19780 KB Output is correct
10 Correct 9 ms 12240 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 44 ms 20092 KB Output is correct
13 Correct 51 ms 21592 KB Output is correct
14 Execution timed out 1101 ms 18864 KB Time limit exceeded
15 Halted 0 ms 0 KB -