oj.uz

Submission #543935

# Submission time Handle Problem Language Result Execution time Memory
543935 2022-03-31T16:12:37 Z Olympia Senior Postmen (BOI14_postmen) C++17
38 / 100
 500 ms 17524 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>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O1")
#pragma GCC optimization ("unroll-loops")

using namespace std;

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

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

Compilation message

postmen.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("O1")
      | 
postmen.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   17 | #pragma GCC optimization ("unroll-loops")
      | 
postmen.cpp: In function 'int main()':
postmen.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         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 8 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 17 ms 12628 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 144 ms 14212 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 8 ms 12116 KB Output is correct
12 Correct 77 ms 14428 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11996 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11992 KB Output is correct
4 Correct 7 ms 12192 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 8 ms 12116 KB Output is correct
7 Correct 17 ms 12500 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 146 ms 14236 KB Output is correct
10 Correct 10 ms 12192 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 77 ms 14540 KB Output is correct
13 Correct 60 ms 17480 KB Output is correct
14 Correct 63 ms 15952 KB Output is correct
15 Execution timed out 941 ms 15952 KB Time limit exceeded
16 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 5 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 8 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 17 ms 12500 KB Output is correct
8 Correct 7 ms 12124 KB Output is correct
9 Correct 155 ms 14328 KB Output is correct
10 Correct 8 ms 12116 KB Output is correct
11 Correct 7 ms 12144 KB Output is correct
12 Correct 75 ms 14536 KB Output is correct
13 Correct 57 ms 17524 KB Output is correct
14 Correct 60 ms 15944 KB Output is correct
15 Execution timed out 928 ms 16132 KB Time limit exceeded
16 Halted 0 ms 0 KB -