oj.uz

Submission #380932

# Submission time Handle Problem Language Result Execution time Memory
380932 2021-03-23T17:13:35 Z usachevd0 Duathlon (APIO18_duathlon) C++14
31 / 100
 155 ms 49256 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto x : v) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; }

const int N = 100005;
int n, m;
vector<int> G[N];
int tin[N], fup[N], timer;
int used[3 * N];
bool cut[N];

vector<int> block[2 * N];
int blocks;

vector<int> stk;
void dfs1(int v, int p = -1)
{
    used[v] = 1;
    tin[v] = fup[v] = timer++;
    stk.push_back(v);
    int cnt_down = 0;
    for (int& u : G[v])
    {
        if (u == p) continue;
        if (!used[u])
        {
            dfs1(u, v);
            chkmin(fup[v], fup[u]);
            if (fup[u] >= tin[v])
            {
                // v is a cut
                ++cnt_down;
                cut[v] = true;
                auto &b = block[blocks++];
                for (; stk.back() != v; stk.pop_back())
                    b.push_back(stk.back());
                b.push_back(v);
            }
        }
        else
        {
            chkmin(fup[v], tin[u]);
        }
    }
    if (p == -1 && cnt_down <= 1)
        cut[v] = false;
}

vector<int> T[3 * N]; // block-cut tree
ll C[3 * N];
ll cnt[3 * N];
ll sum[3 * N];
ll sum2[3 * N];
ll ans;

void add_edge(int u, int v)
{
//    debug(u, v);
    T[u].pb(v);
    T[v].pb(u);
}

void dfs2(int v, int p = -1)
{
    ans += C[v] * (C[v] - 1) * (C[v] - 2); // case 1

    used[v] = 1;
    
    cnt[v] = 1;
    sum[v] = C[v];
    sum2[v] = 0;
    for (int& u : T[v]) if (u != p)
    {
        dfs2(u, v);
        ans += sum2[u] * sum[v] * 2; // case 3
        ans += sum[u] * sum2[v] * 2; // case 3
        cnt[v] += cnt[u];
        sum[v] += sum[u];
        sum2[v] += sum2[u] + sum[u] * C[v];
    }
//    debug(v, cnt[v], sum[v], sum2[v]);
}

ll curSum;
void dfs3(int v, int p = -1)
{
    ans += C[v] * (C[v] - 1) * (curSum - C[v]) * 2; // case 2
    for (int& u : T[v]) if (u != p)
    {
        dfs3(u, v);
    }
    if (v > n) // v --- block
    {
        for (int& u : T[v])
        {
            if (u <= n) // u --- cut
            {
                ans += C[v] * (C[v] - 1); // case 4
            }
        }
    }
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int v = 1; v <= n; ++v) if (!used[v])
    {
        // new component
        dfs1(v);
    }
    for (int bi = 0; bi < blocks; ++bi)
    {
        auto& b = block[bi];
        vector<int> new_block;
        for (auto& v : b)
        {
            if (cut[v])
            {
                add_edge(v, bi + n + 1);
            }
            else
            {
                new_block.push_back(v);
            }
        }
        swap(b, new_block);
        C[bi + n + 1] = b.size();
    }
    for (int v = 1; v <= n; ++v)
        if (cut[v])
            C[v] = 1;
//    mdebug(C + 1, n + blocks);
    ans = 0;
    memset(used, 0, sizeof used);
    for (int bi = 0; bi < blocks; ++bi)
    {
        int v = bi + n + 1;
        if (!used[v])
        {
            dfs2(v);
            curSum = sum[v];
            dfs3(v);
        }
    }
    cout << ans << '\n';
    
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15596 KB Output is correct
2 Correct 10 ms 15596 KB Output is correct
3 Correct 10 ms 15596 KB Output is correct
4 Correct 10 ms 15616 KB Output is correct
5 Correct 10 ms 15596 KB Output is correct
6 Correct 12 ms 15596 KB Output is correct
7 Incorrect 10 ms 15616 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 88 ms 32740 KB Output is correct
2 Correct 97 ms 32740 KB Output is correct
3 Correct 139 ms 36908 KB Output is correct
4 Correct 108 ms 35328 KB Output is correct
5 Correct 99 ms 32744 KB Output is correct
6 Correct 121 ms 38312 KB Output is correct
7 Correct 121 ms 33180 KB Output is correct
8 Correct 141 ms 35836 KB Output is correct
9 Correct 140 ms 31468 KB Output is correct
10 Correct 121 ms 31648 KB Output is correct
11 Correct 99 ms 28512 KB Output is correct
12 Correct 103 ms 28268 KB Output is correct
13 Correct 102 ms 28008 KB Output is correct
14 Correct 79 ms 27752 KB Output is correct
15 Correct 61 ms 26344 KB Output is correct
16 Correct 58 ms 26216 KB Output is correct
17 Correct 14 ms 17132 KB Output is correct
18 Correct 13 ms 17136 KB Output is correct
19 Correct 13 ms 17008 KB Output is correct
20 Correct 12 ms 17008 KB Output is correct
21 Correct 14 ms 17000 KB Output is correct
22 Correct 12 ms 17000 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15852 KB Output is correct
2 Correct 11 ms 15852 KB Output is correct
3 Correct 12 ms 15852 KB Output is correct
4 Correct 11 ms 15980 KB Output is correct
5 Correct 11 ms 15852 KB Output is correct
6 Correct 11 ms 15852 KB Output is correct
7 Correct 11 ms 15980 KB Output is correct
8 Correct 11 ms 15852 KB Output is correct
9 Correct 11 ms 15852 KB Output is correct
10 Correct 11 ms 15852 KB Output is correct
11 Correct 11 ms 15852 KB Output is correct
12 Correct 11 ms 15852 KB Output is correct
13 Correct 11 ms 15852 KB Output is correct
14 Correct 11 ms 15852 KB Output is correct
15 Correct 11 ms 15852 KB Output is correct
16 Correct 12 ms 15724 KB Output is correct
17 Correct 11 ms 15852 KB Output is correct
18 Correct 11 ms 15852 KB Output is correct
19 Correct 11 ms 15852 KB Output is correct
20 Correct 12 ms 15852 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 33644 KB Output is correct
2 Correct 132 ms 33644 KB Output is correct
3 Correct 129 ms 33772 KB Output is correct
4 Correct 137 ms 33644 KB Output is correct
5 Correct 134 ms 33644 KB Output is correct
6 Correct 155 ms 49256 KB Output is correct
7 Correct 149 ms 39272 KB Output is correct
8 Correct 150 ms 37740 KB Output is correct
9 Correct 152 ms 36332 KB Output is correct
10 Correct 133 ms 33648 KB Output is correct
11 Correct 121 ms 33644 KB Output is correct
12 Correct 123 ms 33772 KB Output is correct
13 Correct 131 ms 33644 KB Output is correct
14 Correct 119 ms 32748 KB Output is correct
15 Correct 104 ms 31612 KB Output is correct
16 Correct 61 ms 27496 KB Output is correct
17 Correct 75 ms 31076 KB Output is correct
18 Correct 79 ms 31064 KB Output is correct
19 Correct 73 ms 31200 KB Output is correct
20 Correct 72 ms 31084 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 33664 KB Output is correct
2 Correct 149 ms 33516 KB Output is correct
3 Incorrect 133 ms 32364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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