oj.uz

Submission #698831

# Submission time Handle Problem Language Result Execution time Memory
698831 2023-02-14T11:23:57 Z Hanksburger Duathlon (APIO18_duathlon) C++17
0 / 100
 89 ms 26700 KB 
#include <bits/stdc++.h>
using namespace std;
long long sz[200005], tin[100005], low[100005], timer, bccs, cnt, ans, n, m;
vector<long long> bcc[200005], adj[100005];
stack<long long> s;
void dfs(long long u, long long p)
{
    cnt++;
    low[u]=tin[u]=(++timer);
    s.push(u);
    for (long long v:adj[u])
    {
        if (v==p)
            continue;
        if (tin[v])
        {
            low[u]=min(low[u], tin[v]);
            continue;
        }
        dfs(v, u);
        low[u]=min(low[u], low[v]);
        if (low[v]>=tin[u])
        {
            bcc[u].push_back(n+(++bccs));
            while (bcc[n+bccs].empty() || bcc[n+bccs].back()!=v)
            {
                bcc[n+bccs].push_back(s.top());
                s.pop();
            }
        }
    }
}
void dfs2(long long u)
{
    sz[u]=(u<=n);
    for (long long v:bcc[u])
    {
        dfs2(v);
        sz[u]+=sz[v];
        if (u>n)
            ans+=bcc[u].size()*sz[v]*(sz[v]-1);
    }
    if (u>n)
        ans+=bcc[u].size()*(cnt-sz[u])*(cnt-sz[u]-1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (long long i=1; i<=m; i++)
    {
        long long u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (long long i=1; i<=n; i++)
    {
        if (!tin[i])
        {
            cnt=0;
            dfs(i, 0);
            dfs2(i);
        }
    }
    cout << n*(n-1)*(n-2)-ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 25532 KB Output is correct
2 Correct 65 ms 26676 KB Output is correct
3 Incorrect 80 ms 23456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 19144 KB Output is correct
2 Correct 81 ms 19164 KB Output is correct
3 Correct 89 ms 19380 KB Output is correct
4 Correct 68 ms 19108 KB Output is correct
5 Correct 67 ms 19144 KB Output is correct
6 Correct 88 ms 26700 KB Output is correct
7 Correct 79 ms 23952 KB Output is correct
8 Correct 75 ms 22796 KB Output is correct
9 Correct 73 ms 21556 KB Output is correct
10 Incorrect 73 ms 19148 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7468 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 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 Correct 4 ms 7384 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7364 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 5 ms 7508 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 4 ms 7508 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct
16 Incorrect 5 ms 7380 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 19188 KB Output is correct
2 Correct 72 ms 19288 KB Output is correct
3 Correct 81 ms 18648 KB Output is correct
4 Correct 89 ms 18968 KB Output is correct
5 Correct 73 ms 17644 KB Output is correct
6 Correct 65 ms 16804 KB Output is correct
7 Correct 62 ms 16460 KB Output is correct
8 Correct 57 ms 16004 KB Output is correct
9 Correct 53 ms 15952 KB Output is correct
10 Correct 59 ms 15820 KB Output is correct
11 Correct 58 ms 15648 KB Output is correct
12 Correct 62 ms 15588 KB Output is correct
13 Correct 52 ms 15512 KB Output is correct
14 Correct 54 ms 18252 KB Output is correct
15 Correct 86 ms 25036 KB Output is correct
16 Correct 88 ms 23480 KB Output is correct
17 Correct 86 ms 23932 KB Output is correct
18 Correct 83 ms 22348 KB Output is correct
19 Incorrect 75 ms 18900 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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