oj.uz

Submission #676225

# Submission time Handle Problem Language Result Execution time Memory
676225 2022-12-29T21:50:38 Z danikoynov Duathlon (APIO18_duathlon) C++14
31 / 100
 190 ms 35460 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

int n, m, tin[maxn], low[maxn], timer, bcc, cnt;
vector < int > g[maxn * 2], bcc_graph[maxn];
stack < int > st;

void add_edge(int v, int u)
{
    bcc_graph[v].push_back(u);
    bcc_graph[u].push_back(v);
}

void dfs(int v, int p)
{
    tin[v] = low[v] = ++ timer;
    st.push(v);
    cnt ++;
    for (int u : g[v])
    {
        if (u == p)
            continue;
        if (tin[u])
        {
            low[v] = min(low[v], tin[u]);
        }
        else
        {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (low[u] >= tin[v])
            {
                bcc ++;
                add_edge(v, n + bcc);
                while(!bcc_graph[n + bcc].size() || st.top() != v)
                {
                    add_edge(st.top(), n + bcc);
                    st.pop();
                }
            }
        }
    }
}


ll ans = 0;
ll sub[maxn];
void bad_triple(int v, int p)
{
    if (v <= n)
        sub[v] = 1;
    for (int u : bcc_graph[v])
    {
        if (u == p)
            continue;
        bad_triple(u, v);
        sub[v] += sub[u];
        if (v > n)
        {
            ans = ans - (ll)((ll)bcc_graph[v].size() - 1) * (ll)(sub[u]) *(ll)(sub[u] - 1);
            ///cout << v << " : " << u << " " << sub[u] << " " << (ll)((ll)bcc_graph[v].size() - 1) * (ll)(sub[u]) *(ll)(sub[u] - 1) << endl;
        }
    }
    if (v > n)
    {
        ans = ans - (ll)((ll)bcc_graph[v].size() - 1) * (ll)(cnt - sub[v]) * (ll)(cnt - sub[v] - 1);
    }

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

    for (int i = 1; i <= n; i ++)
    {
        if (tin[i])
            continue;
        cnt = 0;
        dfs(i, 0);

        ans += (ll)(cnt) * (ll)(cnt - 1) * (ll)(cnt - 2);
        bad_triple(i, 0);
    }

    cout << ans << endl;

}

int main()
{
    solve();
    return 0;
}

/**
6 4
1 2
2 3
4
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14408 KB Output is correct
2 Correct 8 ms 14404 KB Output is correct
3 Correct 8 ms 14404 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 7 ms 14408 KB Output is correct
6 Correct 8 ms 14392 KB Output is correct
7 Incorrect 7 ms 14292 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 126 ms 32900 KB Output is correct
2 Correct 110 ms 32880 KB Output is correct
3 Correct 116 ms 31684 KB Output is correct
4 Correct 133 ms 31368 KB Output is correct
5 Correct 118 ms 28856 KB Output is correct
6 Correct 142 ms 30664 KB Output is correct
7 Correct 121 ms 28680 KB Output is correct
8 Correct 122 ms 29024 KB Output is correct
9 Correct 130 ms 27140 KB Output is correct
10 Correct 157 ms 27472 KB Output is correct
11 Correct 132 ms 25072 KB Output is correct
12 Correct 119 ms 24828 KB Output is correct
13 Correct 105 ms 24860 KB Output is correct
14 Correct 121 ms 24544 KB Output is correct
15 Correct 87 ms 23448 KB Output is correct
16 Correct 95 ms 23236 KB Output is correct
17 Correct 11 ms 16320 KB Output is correct
18 Correct 13 ms 16316 KB Output is correct
19 Correct 12 ms 16340 KB Output is correct
20 Correct 12 ms 16340 KB Output is correct
21 Correct 10 ms 16324 KB Output is correct
22 Correct 10 ms 16340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 10 ms 14656 KB Output is correct
3 Correct 11 ms 14424 KB Output is correct
4 Correct 9 ms 14548 KB Output is correct
5 Correct 10 ms 14544 KB Output is correct
6 Correct 9 ms 14584 KB Output is correct
7 Correct 9 ms 14548 KB Output is correct
8 Correct 10 ms 14576 KB Output is correct
9 Correct 10 ms 14544 KB Output is correct
10 Correct 11 ms 14480 KB Output is correct
11 Correct 10 ms 14540 KB Output is correct
12 Correct 11 ms 14444 KB Output is correct
13 Correct 10 ms 14420 KB Output is correct
14 Correct 10 ms 14408 KB Output is correct
15 Correct 9 ms 14420 KB Output is correct
16 Correct 11 ms 14504 KB Output is correct
17 Correct 10 ms 14536 KB Output is correct
18 Correct 10 ms 14520 KB Output is correct
19 Correct 9 ms 14500 KB Output is correct
20 Correct 9 ms 14548 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 27204 KB Output is correct
2 Correct 157 ms 27212 KB Output is correct
3 Correct 142 ms 27240 KB Output is correct
4 Correct 149 ms 27172 KB Output is correct
5 Correct 158 ms 27140 KB Output is correct
6 Correct 146 ms 35460 KB Output is correct
7 Correct 158 ms 32624 KB Output is correct
8 Correct 152 ms 31200 KB Output is correct
9 Correct 160 ms 29808 KB Output is correct
10 Correct 157 ms 27124 KB Output is correct
11 Correct 156 ms 27120 KB Output is correct
12 Correct 138 ms 27160 KB Output is correct
13 Correct 145 ms 27236 KB Output is correct
14 Correct 125 ms 26760 KB Output is correct
15 Correct 118 ms 26084 KB Output is correct
16 Correct 68 ms 23444 KB Output is correct
17 Correct 105 ms 27808 KB Output is correct
18 Correct 134 ms 27800 KB Output is correct
19 Correct 109 ms 27924 KB Output is correct
20 Correct 108 ms 27844 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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