oj.uz

Submission #733961

# Submission time Handle Problem Language Result Execution time Memory
733961 2023-05-01T12:26:43 Z DAleksa Senior Postmen (BOI14_postmen) C++17
38 / 100
 500 ms 24168 KB 
#include <bits/stdc++.h>

using namespace std;

struct edge {
    int v;
    int id;
};

const int N = 5e5 + 10;
vector<edge> g[N];
int n, m;
vector<int> eulerian_cycle;
bool mark[N];
int cnt[N];
int id = 0;
int boze_pomozi = 0;

void find_eulerian_cycle(int u) {
    boze_pomozi++;
    for(edge v : g[u]) {
        if(mark[v.id]) continue;
        mark[v.id] = true;
        find_eulerian_cycle(v.v);
        eulerian_cycle.push_back(v.v);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, id});
        g[v].push_back({u, id++});
    }
    find_eulerian_cycle(1);
    assert(boze_pomozi <= 10000000);
    eulerian_cycle.push_back(1);
    stack<int> stk;
    stk.push(eulerian_cycle[0]);
    cnt[eulerian_cycle[0]]++;
    for(int i = 1; i < eulerian_cycle.size(); i++) {
        if(cnt[eulerian_cycle[i]] > 0) {
            cout << eulerian_cycle[i] << " ";
            while(stk.top() != eulerian_cycle[i]) {
                cout << stk.top() << " ";
                cnt[stk.top()]--;
                stk.pop();
            }
            cout << "\n";
        } else {
            cnt[eulerian_cycle[i]]++;
            stk.push(eulerian_cycle[i]);
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 8 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 9 ms 12372 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 12464 KB Output is correct
7 Correct 13 ms 13780 KB Output is correct
8 Correct 8 ms 12200 KB Output is correct
9 Correct 84 ms 21940 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 8 ms 12244 KB Output is correct
12 Correct 53 ms 22452 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 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 9 ms 12372 KB Output is correct
5 Correct 7 ms 12196 KB Output is correct
6 Correct 9 ms 12556 KB Output is correct
7 Correct 17 ms 13692 KB Output is correct
8 Correct 8 ms 12204 KB Output is correct
9 Correct 85 ms 21996 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 11 ms 12332 KB Output is correct
12 Correct 57 ms 22400 KB Output is correct
13 Correct 58 ms 24132 KB Output is correct
14 Correct 75 ms 20516 KB Output is correct
15 Execution timed out 1063 ms 22684 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12060 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 10 ms 12372 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 11 ms 12500 KB Output is correct
7 Correct 17 ms 13744 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 81 ms 22036 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 8 ms 12244 KB Output is correct
12 Correct 55 ms 22548 KB Output is correct
13 Correct 60 ms 24168 KB Output is correct
14 Correct 65 ms 20496 KB Output is correct
15 Execution timed out 1069 ms 22472 KB Time limit exceeded
16 Halted 0 ms 0 KB -