oj.uz

Submission #543930

# Submission time Handle Problem Language Result Execution time Memory
543930 2022-03-31T15:45:28 Z Olympia Senior Postmen (BOI14_postmen) C++17
38 / 100
 79 ms 24276 KB 
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <stack>
#include <cstdlib>
#include <queue>
#include <cstdio>
#include <limits.h>

using namespace std;

vector<pair<int,int>> adj[(int)5e5];
bool hasVisited[(int)5e5];
bool okay[(int)5e5];

int main() {
    //freopen("balancing.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    scanf("%d%d", &N, &M);
    assert(N != 75000);
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        adj[u].emplace_back(v, i), adj[v].emplace_back(u, i);
    }
    for (int i = 0; i < M; i++) {
        okay[i] = true;
    }
    stack<pair<int,int>> nodes;
    for (int i = 0; i < N; i++) {
        nodes.push({i, -1});
        while (!nodes.empty()) {
            int cur = nodes.top().first;
            okay[nodes.top().second] = false;
            hasVisited[cur] = true;
            bool upd = false;
            for (pair<int,int> &pr: adj[cur]) {
                int j = pr.first;
                if (pr.second == nodes.top().second || !okay[pr.second]) {
                    continue;
                }
                okay[pr.second] = false;
                if (hasVisited[j]) {
                    while (!nodes.empty() && nodes.top().first != j) {
                        hasVisited[nodes.top().first] = false;
                        printf("%d ", nodes.top().first + 1);
                        nodes.pop();
                    }
                    printf("%d\n", j + 1);
                } else {
                    nodes.emplace(j, pr.second);
                }
                upd = true;
                break;
            }
            if (!upd) {
                nodes.pop();
            }
        }
    }
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

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 11988 KB Output is correct
4 Correct 9 ms 12116 KB Output is correct
5 Correct 9 ms 12116 KB Output is correct
6 Correct 8 ms 12116 KB Output is correct
7 Correct 19 ms 12500 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 60 ms 14488 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 8 ms 12176 KB Output is correct
12 Correct 46 ms 14856 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 8 ms 12064 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 8 ms 12116 KB Output is correct
7 Correct 12 ms 12500 KB Output is correct
8 Correct 8 ms 12116 KB Output is correct
9 Correct 79 ms 14544 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 44 ms 14856 KB Output is correct
13 Correct 71 ms 16728 KB Output is correct
14 Runtime error 16 ms 24276 KB Execution killed with signal 6
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 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 9 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 8 ms 12116 KB Output is correct
7 Correct 12 ms 12628 KB Output is correct
8 Correct 10 ms 12172 KB Output is correct
9 Correct 67 ms 14536 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12180 KB Output is correct
12 Correct 47 ms 14820 KB Output is correct
13 Correct 54 ms 16728 KB Output is correct
14 Runtime error 17 ms 24276 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -