oj.uz

답안 #543948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
543948 2022-03-31T16:59:59 Z Olympia 어르신 집배원 (BOI14_postmen) C++17
100 / 100
 472 ms 40652 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<pair<int,int>> adj[(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].emplace_back(v, i), adj[v].emplace_back(u, i);
    }
    for (int i = 0; i < M; i++) {
        okay[i] = true;
    }
    int nodes[(int)5e5];
    for (int i = 0; i < N; i++) {
        int index = 0;
        nodes[index] = i;
        bool upd;
        while (index != -1) {
            int cur = nodes[index];
            hasVisited[cur] = true;
            upd = false;
            while (!adj[cur].empty()) {
                pair<int,int> pr = adj[cur].back();
                adj[cur].pop_back();
                int j = pr.first;
                if (!okay[pr.second]) {
                    continue;
                }
                okay[pr.second] = false;
                if (hasVisited[j]) {
                    while (nodes[index] != j) {
                        hasVisited[nodes[index]] = false;
                        printf("%d ", nodes[index] + 1);
                        index--;
                    }
                    printf("%d\n", j + 1);
                } else {
                    nodes[++index] = j;
                }
                upd = true;
                break;
            }
            if (!upd) {
                index--;
            }
        }
    }
}

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:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Correct 7 ms 13908 KB Output is correct
3 Correct 7 ms 13908 KB Output is correct
4 Correct 9 ms 14108 KB Output is correct
5 Correct 8 ms 14036 KB Output is correct
6 Correct 11 ms 14164 KB Output is correct
7 Correct 14 ms 14548 KB Output is correct
8 Correct 9 ms 14036 KB Output is correct
9 Correct 35 ms 16496 KB Output is correct
10 Correct 8 ms 14036 KB Output is correct
11 Correct 9 ms 14036 KB Output is correct
12 Correct 39 ms 16724 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 13920 KB Output is correct
2 Correct 7 ms 14036 KB Output is correct
3 Correct 7 ms 14032 KB Output is correct
4 Correct 9 ms 14036 KB Output is correct
5 Correct 10 ms 14036 KB Output is correct
6 Correct 10 ms 14164 KB Output is correct
7 Correct 12 ms 14548 KB Output is correct
8 Correct 8 ms 14036 KB Output is correct
9 Correct 34 ms 16460 KB Output is correct
10 Correct 9 ms 14108 KB Output is correct
11 Correct 8 ms 14036 KB Output is correct
12 Correct 40 ms 16772 KB Output is correct
13 Correct 77 ms 17912 KB Output is correct
14 Correct 51 ms 17584 KB Output is correct
15 Correct 47 ms 17216 KB Output is correct
16 Correct 62 ms 19032 KB Output is correct
17 Correct 73 ms 18508 KB Output is correct
18 Correct 54 ms 18764 KB Output is correct

Subtask #3
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14036 KB Output is correct
2 Correct 7 ms 13908 KB Output is correct
3 Correct 7 ms 13924 KB Output is correct
4 Correct 8 ms 14128 KB Output is correct
5 Correct 8 ms 14016 KB Output is correct
6 Correct 9 ms 14164 KB Output is correct
7 Correct 11 ms 14548 KB Output is correct
8 Correct 9 ms 14092 KB Output is correct
9 Correct 34 ms 16456 KB Output is correct
10 Correct 10 ms 14036 KB Output is correct
11 Correct 9 ms 14036 KB Output is correct
12 Correct 43 ms 16692 KB Output is correct
13 Correct 63 ms 17888 KB Output is correct
14 Correct 54 ms 17532 KB Output is correct
15 Correct 68 ms 17220 KB Output is correct
16 Correct 56 ms 18984 KB Output is correct
17 Correct 54 ms 18596 KB Output is correct
18 Correct 55 ms 18736 KB Output is correct
19 Correct 472 ms 40640 KB Output is correct
20 Correct 448 ms 39064 KB Output is correct
21 Correct 323 ms 35416 KB Output is correct
22 Correct 426 ms 40652 KB Output is correct
23 Correct 174 ms 29056 KB Output is correct
24 Correct 457 ms 38024 KB Output is correct
25 Correct 400 ms 38924 KB Output is correct