oj.uz

Submission #543929

# Submission time Handle Problem Language Result Execution time Memory
543929 2022-03-31T15:44:26 Z Olympia Senior Postmen (BOI14_postmen) C++14
38 / 100
 500 ms 16764 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);
    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:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12080 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 7 ms 12184 KB Output is correct
7 Correct 11 ms 12628 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 62 ms 14540 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 43 ms 14844 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 8 ms 12116 KB Output is correct
5 Correct 8 ms 12120 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 11 ms 12628 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 62 ms 14504 KB Output is correct
10 Correct 8 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 47 ms 14800 KB Output is correct
13 Correct 54 ms 16764 KB Output is correct
14 Correct 56 ms 15664 KB Output is correct
15 Execution timed out 808 ms 15400 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 7 ms 12140 KB Output is correct
7 Correct 12 ms 12540 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 58 ms 14596 KB Output is correct
10 Correct 10 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 45 ms 14824 KB Output is correct
13 Correct 59 ms 16692 KB Output is correct
14 Correct 59 ms 15696 KB Output is correct
15 Execution timed out 826 ms 15424 KB Time limit exceeded
16 Halted 0 ms 0 KB -