oj.uz

Submission #676216

# Submission time Handle Problem Language Result Execution time Memory
676216 2022-12-29T21:37:37 Z danikoynov Duathlon (APIO18_duathlon) C++14
31 / 100
 184 ms 35896 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(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;
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 8 ms 14356 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14400 KB Output is correct
5 Correct 8 ms 14332 KB Output is correct
6 Correct 8 ms 14400 KB Output is correct
7 Incorrect 8 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 14292 KB Output is correct
2 Correct 8 ms 14356 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14400 KB Output is correct
5 Correct 8 ms 14332 KB Output is correct
6 Correct 8 ms 14400 KB Output is correct
7 Incorrect 8 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 109 ms 33220 KB Output is correct
2 Correct 106 ms 33168 KB Output is correct
3 Correct 135 ms 31984 KB Output is correct
4 Correct 131 ms 31724 KB Output is correct
5 Correct 119 ms 29184 KB Output is correct
6 Correct 116 ms 30940 KB Output is correct
7 Correct 141 ms 28980 KB Output is correct
8 Correct 137 ms 29460 KB Output is correct
9 Correct 138 ms 27572 KB Output is correct
10 Correct 123 ms 27748 KB Output is correct
11 Correct 152 ms 25244 KB Output is correct
12 Correct 106 ms 25064 KB Output is correct
13 Correct 88 ms 24896 KB Output is correct
14 Correct 100 ms 24720 KB Output is correct
15 Correct 81 ms 23492 KB Output is correct
16 Correct 73 ms 23268 KB Output is correct
17 Correct 12 ms 16340 KB Output is correct
18 Correct 10 ms 16328 KB Output is correct
19 Correct 11 ms 16320 KB Output is correct
20 Correct 10 ms 16320 KB Output is correct
21 Correct 9 ms 16320 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 11 ms 14548 KB Output is correct
2 Correct 8 ms 14540 KB Output is correct
3 Correct 8 ms 14536 KB Output is correct
4 Correct 8 ms 14540 KB Output is correct
5 Correct 8 ms 14536 KB Output is correct
6 Correct 9 ms 14540 KB Output is correct
7 Correct 10 ms 14544 KB Output is correct
8 Correct 9 ms 14528 KB Output is correct
9 Correct 9 ms 14548 KB Output is correct
10 Correct 9 ms 14508 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 9 ms 14548 KB Output is correct
14 Correct 9 ms 14420 KB Output is correct
15 Correct 8 ms 14516 KB Output is correct
16 Correct 8 ms 14480 KB Output is correct
17 Correct 9 ms 14420 KB Output is correct
18 Correct 8 ms 14548 KB Output is correct
19 Correct 8 ms 14548 KB Output is correct
20 Correct 9 ms 14440 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 27544 KB Output is correct
2 Correct 146 ms 27544 KB Output is correct
3 Correct 122 ms 27556 KB Output is correct
4 Correct 122 ms 27504 KB Output is correct
5 Correct 120 ms 27492 KB Output is correct
6 Correct 167 ms 35896 KB Output is correct
7 Correct 164 ms 33088 KB Output is correct
8 Correct 129 ms 31628 KB Output is correct
9 Correct 135 ms 30232 KB Output is correct
10 Correct 126 ms 27496 KB Output is correct
11 Correct 134 ms 27596 KB Output is correct
12 Correct 141 ms 27596 KB Output is correct
13 Correct 139 ms 27468 KB Output is correct
14 Correct 111 ms 26944 KB Output is correct
15 Correct 97 ms 26212 KB Output is correct
16 Correct 76 ms 23332 KB Output is correct
17 Correct 115 ms 28076 KB Output is correct
18 Correct 111 ms 28100 KB Output is correct
19 Correct 127 ms 28180 KB Output is correct
20 Correct 99 ms 28116 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 27596 KB Output is correct
2 Correct 152 ms 27388 KB Output is correct
3 Incorrect 184 ms 26980 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 14292 KB Output is correct
2 Correct 8 ms 14356 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14400 KB Output is correct
5 Correct 8 ms 14332 KB Output is correct
6 Correct 8 ms 14400 KB Output is correct
7 Incorrect 8 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 14292 KB Output is correct
2 Correct 8 ms 14356 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14400 KB Output is correct
5 Correct 8 ms 14332 KB Output is correct
6 Correct 8 ms 14400 KB Output is correct
7 Incorrect 8 ms 14292 KB Output isn't correct
8 Halted 0 ms 0 KB -