oj.uz

Submission #389430

# Submission time Handle Problem Language Result Execution time Memory
389430 2021-04-14T04:38:13 Z phathnv Duathlon (APIO18_duathlon) C++11
31 / 100
 163 ms 30340 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int n, m, sz, cnt[N], low[N], num[N], timer, numComp;
vector<int> adj[N], adj2[N];
stack<int> st;
ll answer;

void Dfs1(int u){
    low[u] = num[u] = ++timer;
    st.push(u);
    sz++;
    for(int v : adj[u]){
        if (!num[v]){
            Dfs1(v);
            low[u] = min(low[u], low[v]);
            if (low[v] >= num[u]){
                ++numComp;
                adj2[u].push_back(n + numComp);
                while (st.top() != u){
                    adj2[n + numComp].push_back(st.top());
                    st.pop();
                }
            }
        } else {
            low[u] = min(low[u], num[v]);
        }
    }
}

void Dfs2(int u){
    cnt[u] = (u <= n);
    for(int v : adj2[u]){
        Dfs2(v);
        cnt[u] += cnt[v];
        if (u > n)
            answer -= (ll) adj2[u].size() * cnt[v] * (cnt[v] - 1);
    }
    if (u > n)
        answer -= (ll) adj2[u].size() * (sz - cnt[u]) * (sz - cnt[u] - 1);
}

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

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= n; i++){
        if (num[i])
            continue;
        sz = 0;
        Dfs1(i);
        Dfs2(i);
        answer += (ll) sz * (sz - 1) * (sz - 2);
    }

    cout << answer;
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9624 KB Output is correct
5 Correct 7 ms 9664 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Incorrect 6 ms 9724 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 85 ms 25664 KB Output is correct
2 Correct 90 ms 25468 KB Output is correct
3 Correct 121 ms 25192 KB Output is correct
4 Correct 105 ms 24904 KB Output is correct
5 Correct 98 ms 21824 KB Output is correct
6 Correct 101 ms 24404 KB Output is correct
7 Correct 90 ms 22712 KB Output is correct
8 Correct 92 ms 23164 KB Output is correct
9 Correct 100 ms 20968 KB Output is correct
10 Correct 92 ms 20932 KB Output is correct
11 Correct 84 ms 18212 KB Output is correct
12 Correct 72 ms 18104 KB Output is correct
13 Correct 67 ms 17996 KB Output is correct
14 Correct 67 ms 17776 KB Output is correct
15 Correct 54 ms 17036 KB Output is correct
16 Correct 53 ms 16708 KB Output is correct
17 Correct 9 ms 11252 KB Output is correct
18 Correct 9 ms 11248 KB Output is correct
19 Correct 9 ms 11212 KB Output is correct
20 Correct 9 ms 11340 KB Output is correct
21 Correct 10 ms 11212 KB Output is correct
22 Correct 9 ms 11212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9824 KB Output is correct
2 Correct 6 ms 9736 KB Output is correct
3 Correct 6 ms 9804 KB Output is correct
4 Correct 7 ms 9932 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 8 ms 9804 KB Output is correct
7 Correct 8 ms 9912 KB Output is correct
8 Correct 7 ms 9804 KB Output is correct
9 Correct 7 ms 9804 KB Output is correct
10 Correct 6 ms 9804 KB Output is correct
11 Correct 6 ms 9828 KB Output is correct
12 Correct 7 ms 9804 KB Output is correct
13 Correct 6 ms 9728 KB Output is correct
14 Correct 6 ms 9744 KB Output is correct
15 Correct 6 ms 9808 KB Output is correct
16 Correct 6 ms 9728 KB Output is correct
17 Correct 6 ms 9804 KB Output is correct
18 Correct 6 ms 9804 KB Output is correct
19 Correct 6 ms 9720 KB Output is correct
20 Correct 6 ms 9808 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 20456 KB Output is correct
2 Correct 96 ms 20420 KB Output is correct
3 Correct 86 ms 20476 KB Output is correct
4 Correct 89 ms 20420 KB Output is correct
5 Correct 87 ms 20428 KB Output is correct
6 Correct 106 ms 30340 KB Output is correct
7 Correct 163 ms 26728 KB Output is correct
8 Correct 105 ms 25248 KB Output is correct
9 Correct 153 ms 23672 KB Output is correct
10 Correct 93 ms 20504 KB Output is correct
11 Correct 99 ms 20420 KB Output is correct
12 Correct 93 ms 20460 KB Output is correct
13 Correct 103 ms 20492 KB Output is correct
14 Correct 91 ms 20028 KB Output is correct
15 Correct 102 ms 19396 KB Output is correct
16 Correct 64 ms 17060 KB Output is correct
17 Correct 61 ms 19572 KB Output is correct
18 Correct 66 ms 19508 KB Output is correct
19 Correct 79 ms 19684 KB Output is correct
20 Correct 79 ms 19584 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 20508 KB Output is correct
2 Correct 130 ms 20784 KB Output is correct
3 Incorrect 132 ms 20116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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