oj.uz

Submission #742806

# Submission time Handle Problem Language Result Execution time Memory
742806 2023-05-17T01:54:04 Z becaido Duathlon (APIO18_duathlon) C++17
31 / 100
 185 ms 50336 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;

int n, m;
ll ans;
bool vs[SIZE];
int gn, sz[SIZE];
vector<int> adj[SIZE], gadj[SIZE];

ll P(int x, int y) {
    if (y < 0 || y > x) return 0;
    if (y == 2) return 1ll * x * (x - 1);
    if (y == 3) return 1ll * x * (x - 1) * (x - 2);
}

struct VBCC { // need adj
    int n, dfcnt = 0, bccnt = 0;
    vector<int> dfn, low, st;
    vector<vector<int>> bcc;
    VBCC() {}
    VBCC(int n) : n(n) {
        dfn = low = vector<int>(n + 1, 0);
        bcc = vector<vector<int>>(n + 1, vector<int>());
    }
    void tarjan(int pos, int fa) {
        dfn[pos] = low[pos] = ++dfcnt;
        st.emplace_back(pos);
        for (int np : adj[pos]) {
            if (np != fa) {
                if (dfn[np] == 0) {
                    tarjan(np, pos);
                    low[pos] = min(low[pos], low[np]);
                    if (dfn[pos] <= low[np]) {
                        bccnt++;
                        while (1) {
                            int x = st.back();
                            bcc[x].emplace_back(bccnt);
                            st.pop_back();
                            if (x == np) {
                                break;
                            }
                        }
                        bcc[pos].emplace_back(bccnt);
                    }
                } else {
                    low[pos] = min(low[pos], dfn[np]);
                }
            }
        }
        if (pos == fa) {
            st.pop_back();
            if (bcc[pos].size() == 0) {
                bcc[pos].emplace_back(++bccnt);
            }
        }
    }
    void work() {
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == 0) {
                tarjan(i, i);
            }
        }
        gn = bccnt;
        FOR (i, 1, n) {
            if (bcc[i].size() == 1) sz[bcc[i][0]]++;
            else {
                sz[++gn] = 1;
                for (int x : bcc[i]) {
                    gadj[gn].pb(x);
                    gadj[x].pb(gn);
                }
            }
        }
        FOR (i, 1, gn) if (!vs[i]) {
            int all = 0;
            auto pre = [&](auto pre, int pos, int fa)->void {
                all += sz[pos];
                for (int np : gadj[pos]) if (np != fa) pre(pre, np, pos);
            };
            pre(pre, i, i);
            auto dfs = [&](auto dfs, int pos, int fa)->int {
                vs[pos] = 1;
                vector<int> v;
                int sum = sz[pos];
                for (int np : gadj[pos]) if (np != fa) {
                    int w = dfs(dfs, np, pos);
                    sum += w;
                    v.pb(w);
                }
                v.pb(all - sum);
                ans += P(sz[pos], 3);
                if (pos > bccnt) {
                    for (int np : gadj[pos]) ans += P(sz[np], 2);
                }
                for (int x : v) {
                    ans += 2 * P(sz[pos], 2) * x;
                    ans += 1ll * sz[pos] * x * (all - sz[pos] - x);
                }
                return sum;
            };
            dfs(dfs, i, i);
        }
    }
} G;

void solve() {
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    G = VBCC(n);
    G.work();
    cout << ans << '\n';
}

int main() {
    Waimai;
    solve();
}

Compilation message

count_triplets.cpp: In function 'long long int P(int, int)':
count_triplets.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9724 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9724 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9616 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Incorrect 6 ms 9684 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 78 ms 26440 KB Output is correct
2 Correct 88 ms 26480 KB Output is correct
3 Correct 108 ms 35440 KB Output is correct
4 Correct 84 ms 28128 KB Output is correct
5 Correct 92 ms 30384 KB Output is correct
6 Correct 117 ms 36936 KB Output is correct
7 Correct 111 ms 29056 KB Output is correct
8 Correct 112 ms 32804 KB Output is correct
9 Correct 114 ms 26864 KB Output is correct
10 Correct 100 ms 27740 KB Output is correct
11 Correct 72 ms 22348 KB Output is correct
12 Correct 70 ms 22368 KB Output is correct
13 Correct 62 ms 21664 KB Output is correct
14 Correct 68 ms 21624 KB Output is correct
15 Correct 46 ms 20304 KB Output is correct
16 Correct 47 ms 20292 KB Output is correct
17 Correct 16 ms 16376 KB Output is correct
18 Correct 18 ms 16376 KB Output is correct
19 Correct 16 ms 16468 KB Output is correct
20 Correct 16 ms 16448 KB Output is correct
21 Correct 16 ms 16372 KB Output is correct
22 Correct 16 ms 16376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9764 KB Output is correct
4 Correct 8 ms 10068 KB Output is correct
5 Correct 7 ms 9984 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 7 ms 10068 KB Output is correct
8 Correct 8 ms 9860 KB Output is correct
9 Correct 7 ms 9852 KB Output is correct
10 Correct 7 ms 9856 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 7 ms 9812 KB Output is correct
15 Correct 7 ms 9852 KB Output is correct
16 Correct 6 ms 9812 KB Output is correct
17 Correct 7 ms 9856 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 6 ms 9812 KB Output is correct
20 Correct 7 ms 9812 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 26016 KB Output is correct
2 Correct 116 ms 26060 KB Output is correct
3 Correct 120 ms 26056 KB Output is correct
4 Correct 119 ms 26108 KB Output is correct
5 Correct 121 ms 26068 KB Output is correct
6 Correct 185 ms 50336 KB Output is correct
7 Correct 161 ms 35272 KB Output is correct
8 Correct 151 ms 33060 KB Output is correct
9 Correct 133 ms 30784 KB Output is correct
10 Correct 110 ms 26124 KB Output is correct
11 Correct 120 ms 26036 KB Output is correct
12 Correct 135 ms 26016 KB Output is correct
13 Correct 118 ms 26120 KB Output is correct
14 Correct 99 ms 25352 KB Output is correct
15 Correct 101 ms 24284 KB Output is correct
16 Correct 55 ms 21160 KB Output is correct
17 Correct 59 ms 25840 KB Output is correct
18 Correct 58 ms 25732 KB Output is correct
19 Correct 60 ms 25776 KB Output is correct
20 Correct 62 ms 25628 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 26028 KB Output is correct
2 Correct 145 ms 26384 KB Output is correct
3 Incorrect 114 ms 25688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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