oj.uz

Submission #757274

# Submission time Handle Problem Language Result Execution time Memory
757274 2023-06-13T00:28:44 Z shjgkwo Duathlon (APIO18_duathlon) C++17
31 / 100
 286 ms 59956 KB 
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>

using namespace std;

const int MAXN = 100010;

vector<int> edge[MAXN];

map<int, int> bcce[MAXN];

int bcc_cnt = 0;

int pre_cnt = 0;
int pre[MAXN];
int low[MAXN];
int mypar[MAXN];
int is_sep[MAXN];

long long sum_perm_cnt = 0;
long long node_cnt[MAXN];
long long p[MAXN];

set<int> bcc_node[MAXN];
set<int> node_bcc[MAXN];

stack<pair<int, int> > st;

long long ans = 0;

inline const long long nP3(long long n) {
    return n * (n - 1) * (n - 2);
}

inline const long long nP2(long long n) {
    return n * (n - 1);
}

void dfs(int u, int par) {
    int child = 0, flag = 0;
    mypar[u] = par;
    node_cnt[u] = 1;
    low[u] = pre[u] = ++pre_cnt;
    for(auto &v: edge[u]) {
        if(v == par) continue;
        if(!pre[v]) {
            child++;
            st.push({u, v});
            dfs(v, u);
            node_cnt[u] += node_cnt[v];
            low[u] = min(low[u], low[v]);
            if(pre[u] <= low[v]) {
                bcc_cnt++;
                flag = 1;
                while(st.size() && (st.top().first != u || st.top().second != v)) {
                    int x = st.top().first;
                    int y = st.top().second;
                    bcc_node[bcc_cnt].insert(x);
                    bcc_node[bcc_cnt].insert(y);
                    node_bcc[x].insert(bcc_cnt);
                    node_bcc[y].insert(bcc_cnt);
                    bcce[x][y] = bcc_cnt;
                    bcce[y][x] = bcc_cnt;
                    st.pop();
                }
                int x = st.top().first;
                int y = st.top().second;
                bcc_node[bcc_cnt].insert(x);
                bcc_node[bcc_cnt].insert(y);
                bcce[x][y] = bcc_cnt;
                bcce[y][x] = bcc_cnt;
                st.pop();
                ans += nP3(bcc_node[bcc_cnt].size());
                p[bcc_cnt] = nP2(bcc_node[bcc_cnt].size() - 1);
            }
        }
        else if(pre[u] > pre[v]) {
            st.push({u, v});
            low[u] = min(low[u], pre[v]);
        }
    }
    if(child >= 2 && par == 0) is_sep[u] = 1;
    else if(flag && par != 0) is_sep[u] = 1;
}

int chk[MAXN];
int cached[MAXN];
long long cache_sum[MAXN];

int used[MAXN];

void solve(int origin, int u, int par) {
    long long sum_node_cnt = node_cnt[origin] - node_cnt[u];
    chk[u] = 1;
    long long sep = is_sep[u];

    for (auto &v: edge[u]) {
        if(chk[v]) continue;
        solve(origin, v, u);
        ans += sep * sum_node_cnt * node_cnt[v] * 2;
        sum_node_cnt += node_cnt[v];
    }

    if(!sep) {
        int mybcc = bcce[par][u];
        if(cached[mybcc]) {
            ans += cache_sum[mybcc];
            return;
        }
        long long sum_tmp_node_cnt = 0;
        for(auto &tu: bcc_node[mybcc]) {
            if(bcce[mypar[tu]][tu] != mybcc) {
                long long tmp = node_cnt[origin] - node_cnt[tu];
                cache_sum[mybcc] += sum_tmp_node_cnt * tmp * 2;
                sum_tmp_node_cnt += tmp;
                continue;
            }
            for (auto &v: edge[tu]) {
                if(v == mypar[tu]) continue;
                int anotherbcc = bcce[tu][v];
                if (anotherbcc == mybcc) continue;
                long long tmp = node_cnt[v];
                cache_sum[mybcc] += sum_tmp_node_cnt * tmp * 2;
                sum_tmp_node_cnt += tmp;
            }
        }
        cached[mybcc] = 1;
        ans += cache_sum[mybcc];
        return;
    }

    long long par_node_cnt = node_cnt[origin] - node_cnt[u];
    long long node_sum = par_node_cnt;
    used[bcce[u][par]] = u;
    for(auto &v: edge[u]) {
        if(v == par) continue;
        if(mypar[v] != u) continue;
        node_sum += node_cnt[v];
    }
    
    ans += (node_sum - par_node_cnt) * p[bcce[par][u]] * 2;
    for(auto &v: edge[u]) {
        if(v == par) continue;
        if(mypar[v] != u) continue;
        int bcc = bcce[u][v];
        ans += (node_sum - node_cnt[v]) * p[bcc] * 2;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        if (pre[i]) {
            continue;
        }
        dfs(i, 0);
    }
    for (int i = 1; i <= n; i++) {
        if (chk[i]) {
            continue;
        }
        solve(i, i, 0);
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16692 KB Output is correct
4 Correct 12 ms 16764 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Incorrect 10 ms 16740 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 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16692 KB Output is correct
4 Correct 12 ms 16764 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Incorrect 10 ms 16740 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 275 ms 59956 KB Output is correct
2 Correct 238 ms 59840 KB Output is correct
3 Correct 195 ms 51464 KB Output is correct
4 Correct 223 ms 55844 KB Output is correct
5 Correct 211 ms 48108 KB Output is correct
6 Correct 199 ms 48252 KB Output is correct
7 Correct 157 ms 45940 KB Output is correct
8 Correct 179 ms 47312 KB Output is correct
9 Correct 180 ms 44108 KB Output is correct
10 Correct 183 ms 45576 KB Output is correct
11 Correct 135 ms 41128 KB Output is correct
12 Correct 130 ms 40724 KB Output is correct
13 Correct 132 ms 39816 KB Output is correct
14 Correct 131 ms 39284 KB Output is correct
15 Correct 99 ms 36028 KB Output is correct
16 Correct 100 ms 35912 KB Output is correct
17 Correct 30 ms 23764 KB Output is correct
18 Correct 29 ms 23764 KB Output is correct
19 Correct 32 ms 23728 KB Output is correct
20 Correct 31 ms 23788 KB Output is correct
21 Correct 36 ms 23828 KB Output is correct
22 Correct 29 ms 23792 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16980 KB Output is correct
2 Correct 9 ms 16980 KB Output is correct
3 Correct 9 ms 16980 KB Output is correct
4 Correct 11 ms 17108 KB Output is correct
5 Correct 10 ms 17108 KB Output is correct
6 Correct 12 ms 17108 KB Output is correct
7 Correct 10 ms 17108 KB Output is correct
8 Correct 11 ms 17108 KB Output is correct
9 Correct 11 ms 17064 KB Output is correct
10 Correct 12 ms 17032 KB Output is correct
11 Correct 10 ms 16980 KB Output is correct
12 Correct 10 ms 16980 KB Output is correct
13 Correct 10 ms 17056 KB Output is correct
14 Correct 9 ms 17008 KB Output is correct
15 Correct 10 ms 16980 KB Output is correct
16 Correct 10 ms 16980 KB Output is correct
17 Correct 12 ms 16980 KB Output is correct
18 Correct 11 ms 16996 KB Output is correct
19 Correct 10 ms 17040 KB Output is correct
20 Correct 11 ms 16980 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 43852 KB Output is correct
2 Correct 158 ms 43832 KB Output is correct
3 Correct 164 ms 43784 KB Output is correct
4 Correct 159 ms 43780 KB Output is correct
5 Correct 165 ms 43864 KB Output is correct
6 Correct 177 ms 52748 KB Output is correct
7 Correct 174 ms 50592 KB Output is correct
8 Correct 168 ms 48840 KB Output is correct
9 Correct 178 ms 47120 KB Output is correct
10 Correct 168 ms 43912 KB Output is correct
11 Correct 142 ms 43872 KB Output is correct
12 Correct 148 ms 43756 KB Output is correct
13 Correct 172 ms 43860 KB Output is correct
14 Correct 152 ms 42208 KB Output is correct
15 Correct 118 ms 40576 KB Output is correct
16 Correct 88 ms 34936 KB Output is correct
17 Correct 286 ms 43332 KB Output is correct
18 Correct 223 ms 43316 KB Output is correct
19 Correct 259 ms 43404 KB Output is correct
20 Correct 198 ms 43428 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 43828 KB Output is correct
2 Correct 146 ms 43740 KB Output is correct
3 Incorrect 180 ms 46580 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 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16692 KB Output is correct
4 Correct 12 ms 16764 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Incorrect 10 ms 16740 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 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16692 KB Output is correct
4 Correct 12 ms 16764 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Incorrect 10 ms 16740 KB Output isn't correct
8 Halted 0 ms 0 KB -