oj.uz

Submission #988376

# Submission time Handle Problem Language Result Execution time Memory
988376 2024-05-24T14:49:50 Z 876pol Duathlon (APIO18_duathlon) C++17
0 / 100
 42 ms 19540 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << "[";
    for (auto it = obj.begin(); it != obj.end(); it++) {
        out << &", "[2 * (it == obj.begin())] << *it;
    }
    return out << "]";
}

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, m;
    cin >> n >> m;
    vec<vec<ll>> graph(n + 1);
    FOR(i, 0, m) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vec<ll> visited(n + 1);
    ll cnt = 0;
    function<void(ll)> dfs = [&](ll curr) {
        visited[curr] = 1;
        cnt++;
        TRAV(e, graph[curr]) {
            if (visited[e]) continue;
            dfs(e);
        }
    };
    dfs(1);
    assert(cnt == n);
    assert(n <= m + 1);
    if (n == m + 1) {
        cout << n * (n - 1) * (n - 2) / 3 << "\n";
    } else if (n == m) {
        cout << n * (n - 1) * (n - 2) << "\n";
    } else {
        assert(false);
    }

    // vec<ll> tin(n + 1), low(n + 1), visited(n + 1);
    // ll tm = 0;
    // function<void(ll, ll)> dfs = [&](ll curr, ll prev) {
    //     low[curr] = tin[curr] = tm++;
    //     visited[curr] = 1;
    //     ll ch = 0;
    //     TRAV(e, graph[curr]) {
    //         if (e == prev) continue;
    //         if (visited[e]) {
    //             low[curr] = min(low[curr], tin[e]);
    //         } else {
    //             dfs(e, curr);
    //             low[curr] = min(low[curr], low[e]);
    //             ch++;
    //         }
    //     }
    // };
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12892 KB Output is correct
2 Correct 34 ms 12880 KB Output is correct
3 Runtime error 42 ms 19540 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 7112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 7248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -