oj.uz

Submission #757259

# Submission time Handle Problem Language Result Execution time Memory
757259 2023-06-12T21:46:23 Z shjgkwo Duathlon (APIO18_duathlon) C++17
31 / 100
 193 ms 53484 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 * 2];

set<int> bcc_node[MAXN * 2];

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);
                    bcce[x][y] = bcc_cnt;
                    bcce[y][x] = bcc_cnt;
                    st.pop();
                }
                if(st.size()) {
                    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];

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) {
        return;
    }
    
    ans += (node_cnt[origin] - node_cnt[u]) * p[bcce[par][u]] * 2;
    for(auto &v: edge[u]) {
        if(mypar[v] != u) continue;
        int bcc = bcce[u][v];
        ans += (node_cnt[origin] - node_cnt[v] - 1) * 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 16800 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 11 ms 16724 KB Output is correct
7 Incorrect 10 ms 16852 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 16800 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 11 ms 16724 KB Output is correct
7 Incorrect 10 ms 16852 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 158 ms 53448 KB Output is correct
2 Correct 187 ms 53484 KB Output is correct
3 Correct 162 ms 48072 KB Output is correct
4 Correct 167 ms 50964 KB Output is correct
5 Correct 159 ms 45516 KB Output is correct
6 Correct 154 ms 46676 KB Output is correct
7 Correct 151 ms 44716 KB Output is correct
8 Correct 153 ms 46024 KB Output is correct
9 Correct 162 ms 43008 KB Output is correct
10 Correct 155 ms 43980 KB Output is correct
11 Correct 107 ms 38136 KB Output is correct
12 Correct 127 ms 37684 KB Output is correct
13 Correct 93 ms 36588 KB Output is correct
14 Correct 98 ms 36240 KB Output is correct
15 Correct 88 ms 32756 KB Output is correct
16 Correct 80 ms 32652 KB Output is correct
17 Correct 12 ms 19068 KB Output is correct
18 Correct 12 ms 19192 KB Output is correct
19 Correct 12 ms 19088 KB Output is correct
20 Correct 11 ms 19112 KB Output is correct
21 Correct 13 ms 19156 KB Output is correct
22 Correct 11 ms 19056 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17044 KB Output is correct
2 Correct 10 ms 16980 KB Output is correct
3 Correct 12 ms 16972 KB Output is correct
4 Correct 10 ms 17108 KB Output is correct
5 Correct 9 ms 17108 KB Output is correct
6 Correct 9 ms 17108 KB Output is correct
7 Correct 10 ms 17108 KB Output is correct
8 Correct 10 ms 17036 KB Output is correct
9 Correct 9 ms 16980 KB Output is correct
10 Correct 10 ms 16980 KB Output is correct
11 Correct 9 ms 17052 KB Output is correct
12 Correct 9 ms 16996 KB Output is correct
13 Correct 10 ms 16980 KB Output is correct
14 Correct 10 ms 16980 KB Output is correct
15 Correct 9 ms 16980 KB Output is correct
16 Correct 10 ms 16852 KB Output is correct
17 Correct 10 ms 17028 KB Output is correct
18 Correct 9 ms 16980 KB Output is correct
19 Correct 10 ms 16960 KB Output is correct
20 Correct 9 ms 16980 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 42244 KB Output is correct
2 Correct 164 ms 42228 KB Output is correct
3 Correct 132 ms 42196 KB Output is correct
4 Correct 143 ms 42304 KB Output is correct
5 Correct 129 ms 42264 KB Output is correct
6 Correct 141 ms 51512 KB Output is correct
7 Correct 149 ms 48440 KB Output is correct
8 Correct 177 ms 46796 KB Output is correct
9 Correct 148 ms 45260 KB Output is correct
10 Correct 159 ms 42244 KB Output is correct
11 Correct 144 ms 42312 KB Output is correct
12 Correct 162 ms 42220 KB Output is correct
13 Correct 132 ms 42272 KB Output is correct
14 Correct 128 ms 40436 KB Output is correct
15 Correct 119 ms 38444 KB Output is correct
16 Correct 82 ms 31736 KB Output is correct
17 Correct 193 ms 42104 KB Output is correct
18 Correct 184 ms 42340 KB Output is correct
19 Correct 173 ms 42260 KB Output is correct
20 Correct 170 ms 42256 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 16952 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 42196 KB Output is correct
2 Correct 146 ms 42264 KB Output is correct
3 Incorrect 172 ms 42904 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 16800 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 11 ms 16724 KB Output is correct
7 Incorrect 10 ms 16852 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 16800 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 10 ms 16724 KB Output is correct
6 Correct 11 ms 16724 KB Output is correct
7 Incorrect 10 ms 16852 KB Output isn't correct
8 Halted 0 ms 0 KB -