oj.uz

Submission #679126

# Submission time Handle Problem Language Result Execution time Memory
679126 2023-01-07T13:57:18 Z PoonYaPat Duathlon (APIO18_duathlon) C++14
31 / 100
 82 ms 28040 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m,disc[100001],low[100001],sz[200001],cnt,bcc_cnt;
vector<int> adj[100001],bcc[200001];
ll ans,N;

stack<int> st;

void tarjan(int x, int par) {
    st.push(x);
    low[x]=disc[x]=++cnt;
    ++N;

    for (auto s : adj[x]) {
        if (s==par) continue;
        if (disc[s]) low[x]=min(low[x],disc[s]);
        else {
            tarjan(s,x);
            low[x]=min(low[x],low[s]);

            if (low[s]>=disc[x]) {
                ++bcc_cnt;
                bcc[x].push_back(n+bcc_cnt);

                while (st.top()!=x) {
                    bcc[n+bcc_cnt].push_back(st.top());
                    st.pop();
                }
            }
        }
    }
}

void dfs(int x) {
    sz[x]= x>n ? 0 : 1;
    for (auto s : bcc[x]) {
        dfs(s);
        sz[x]+=sz[s];
        if (x>n) ans-=bcc[x].size()*sz[s]*(sz[s]-1);
    }
    if (x>n) ans-=bcc[x].size()*(N-sz[x])*(N-sz[x]-1);
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=0; i<m; ++i) {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i=1; i<=n; ++i) {
        if (!disc[i]) {
            N=0;
            tarjan(i,0);
            ans+=N*(N-1)*(N-2);
            dfs(i);
        }
    }

    cout<<ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7312 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7376 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Incorrect 5 ms 7380 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 56 ms 21912 KB Output is correct
2 Correct 50 ms 21948 KB Output is correct
3 Correct 82 ms 21600 KB Output is correct
4 Correct 74 ms 22592 KB Output is correct
5 Correct 58 ms 19448 KB Output is correct
6 Correct 70 ms 22088 KB Output is correct
7 Correct 73 ms 20200 KB Output is correct
8 Correct 78 ms 20796 KB Output is correct
9 Correct 71 ms 18580 KB Output is correct
10 Correct 75 ms 18584 KB Output is correct
11 Correct 57 ms 15820 KB Output is correct
12 Correct 52 ms 15672 KB Output is correct
13 Correct 47 ms 15592 KB Output is correct
14 Correct 44 ms 15340 KB Output is correct
15 Correct 51 ms 14612 KB Output is correct
16 Correct 42 ms 14424 KB Output is correct
17 Correct 6 ms 8916 KB Output is correct
18 Correct 6 ms 8916 KB Output is correct
19 Correct 6 ms 8916 KB Output is correct
20 Correct 6 ms 8916 KB Output is correct
21 Correct 6 ms 8916 KB Output is correct
22 Correct 6 ms 8916 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7388 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 6 ms 7516 KB Output is correct
6 Correct 5 ms 7636 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 4 ms 7516 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7456 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 7468 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 4 ms 7384 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 16792 KB Output is correct
2 Correct 66 ms 18124 KB Output is correct
3 Correct 64 ms 18084 KB Output is correct
4 Correct 68 ms 18124 KB Output is correct
5 Correct 67 ms 18064 KB Output is correct
6 Correct 76 ms 28040 KB Output is correct
7 Correct 76 ms 24424 KB Output is correct
8 Correct 76 ms 22852 KB Output is correct
9 Correct 73 ms 21336 KB Output is correct
10 Correct 72 ms 18124 KB Output is correct
11 Correct 67 ms 18252 KB Output is correct
12 Correct 66 ms 18120 KB Output is correct
13 Correct 68 ms 18136 KB Output is correct
14 Correct 64 ms 17676 KB Output is correct
15 Correct 55 ms 17048 KB Output is correct
16 Correct 36 ms 14664 KB Output is correct
17 Correct 44 ms 17228 KB Output is correct
18 Correct 38 ms 17248 KB Output is correct
19 Correct 39 ms 17336 KB Output is correct
20 Correct 39 ms 17144 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16832 KB Output is correct
2 Correct 67 ms 18408 KB Output is correct
3 Incorrect 77 ms 17848 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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