oj.uz

Submission #408602

# Submission time Handle Problem Language Result Execution time Memory
408602 2021-05-19T09:01:57 Z tengiz05 Duathlon (APIO18_duathlon) C++17
31 / 100
 66 ms 10436 KB 
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1e5;
std::vector<int> e[N];
int n, m;
std::vector<bool> vis;
bool cycle;
int sz;
void dfs(int u, int p) {
    sz++;
    vis[u] = true;
    for (auto v : e[u]) {
        if (v == p)continue;
        if (vis[v]) cycle = true;
        else dfs(v, u);
    }
}
i64 ans;
int calc(int u, int p) {
    int cnt = 0;
    for (auto v : e[u]) {
        if (v != p) {
            int t = calc(v, u);
            cnt += t;
            ans += i64(t) * (sz - t - 1);
        }
    }
    ans += i64(cnt) * (sz - cnt - 1);
    return cnt + 1;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vis.assign(n, false);
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            sz = 0;
            cycle = false;
            dfs(i, i);
            if (cycle) {
                ans += i64(sz) * (sz - 1) * (sz - 2);
            } else {
                calc(i, i);
            }
        }
    }
    std::cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 10384 KB Output is correct
2 Correct 66 ms 10436 KB Output is correct
3 Correct 58 ms 8032 KB Output is correct
4 Correct 61 ms 9304 KB Output is correct
5 Correct 59 ms 7348 KB Output is correct
6 Correct 60 ms 7276 KB Output is correct
7 Correct 53 ms 6696 KB Output is correct
8 Correct 55 ms 7072 KB Output is correct
9 Correct 59 ms 6220 KB Output is correct
10 Correct 58 ms 6616 KB Output is correct
11 Correct 43 ms 5812 KB Output is correct
12 Correct 40 ms 5636 KB Output is correct
13 Correct 37 ms 5644 KB Output is correct
14 Correct 38 ms 5432 KB Output is correct
15 Correct 28 ms 5188 KB Output is correct
16 Correct 28 ms 5104 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 3 ms 2636 KB Output is correct
21 Correct 3 ms 2636 KB Output is correct
22 Correct 3 ms 2636 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 3 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 5824 KB Output is correct
2 Correct 52 ms 5888 KB Output is correct
3 Correct 62 ms 5896 KB Output is correct
4 Correct 56 ms 5812 KB Output is correct
5 Correct 56 ms 5772 KB Output is correct
6 Correct 65 ms 8272 KB Output is correct
7 Correct 63 ms 7488 KB Output is correct
8 Correct 61 ms 7112 KB Output is correct
9 Correct 60 ms 6548 KB Output is correct
10 Correct 58 ms 5772 KB Output is correct
11 Correct 50 ms 5896 KB Output is correct
12 Correct 53 ms 5828 KB Output is correct
13 Correct 54 ms 5900 KB Output is correct
14 Correct 49 ms 5740 KB Output is correct
15 Correct 41 ms 5588 KB Output is correct
16 Correct 26 ms 4940 KB Output is correct
17 Correct 35 ms 6152 KB Output is correct
18 Correct 43 ms 6180 KB Output is correct
19 Correct 37 ms 6268 KB Output is correct
20 Correct 36 ms 6208 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Incorrect 2 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5948 KB Output is correct
2 Correct 60 ms 5840 KB Output is correct
3 Incorrect 54 ms 5828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -