oj.uz

Submission #757262

# Submission time Handle Problem Language Result Execution time Memory
757262 2023-06-12T22:05:30 Z shjgkwo Duathlon (APIO18_duathlon) C++17
31 / 100
 252 ms 48904 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];

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();
                }
                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 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12060 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Incorrect 8 ms 11988 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12060 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Incorrect 8 ms 11988 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 252 ms 48868 KB Output is correct
2 Correct 197 ms 48904 KB Output is correct
3 Correct 186 ms 43300 KB Output is correct
4 Correct 169 ms 46280 KB Output is correct
5 Correct 181 ms 39596 KB Output is correct
6 Correct 193 ms 40784 KB Output is correct
7 Correct 160 ms 38764 KB Output is correct
8 Correct 146 ms 40232 KB Output is correct
9 Correct 180 ms 37144 KB Output is correct
10 Correct 151 ms 37976 KB Output is correct
11 Correct 110 ms 32296 KB Output is correct
12 Correct 117 ms 32008 KB Output is correct
13 Correct 102 ms 30924 KB Output is correct
14 Correct 98 ms 30540 KB Output is correct
15 Correct 80 ms 27252 KB Output is correct
16 Correct 102 ms 27168 KB Output is correct
17 Correct 10 ms 14420 KB Output is correct
18 Correct 9 ms 14472 KB Output is correct
19 Correct 9 ms 14420 KB Output is correct
20 Correct 9 ms 14420 KB Output is correct
21 Correct 10 ms 14420 KB Output is correct
22 Correct 9 ms 14356 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 7 ms 12244 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 8 ms 12372 KB Output is correct
5 Correct 7 ms 12332 KB Output is correct
6 Correct 8 ms 12372 KB Output is correct
7 Correct 9 ms 12432 KB Output is correct
8 Correct 8 ms 12372 KB Output is correct
9 Correct 7 ms 12372 KB Output is correct
10 Correct 8 ms 12244 KB Output is correct
11 Correct 9 ms 12244 KB Output is correct
12 Correct 8 ms 12244 KB Output is correct
13 Correct 9 ms 12288 KB Output is correct
14 Correct 7 ms 12244 KB Output is correct
15 Correct 7 ms 12244 KB Output is correct
16 Correct 7 ms 12244 KB Output is correct
17 Correct 7 ms 12340 KB Output is correct
18 Correct 8 ms 12244 KB Output is correct
19 Correct 8 ms 12244 KB Output is correct
20 Correct 7 ms 12244 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 37596 KB Output is correct
2 Correct 142 ms 37596 KB Output is correct
3 Correct 144 ms 37544 KB Output is correct
4 Correct 140 ms 37600 KB Output is correct
5 Correct 126 ms 37496 KB Output is correct
6 Correct 161 ms 46768 KB Output is correct
7 Correct 164 ms 43636 KB Output is correct
8 Correct 157 ms 42156 KB Output is correct
9 Correct 162 ms 40616 KB Output is correct
10 Correct 158 ms 37660 KB Output is correct
11 Correct 156 ms 37516 KB Output is correct
12 Correct 136 ms 37576 KB Output is correct
13 Correct 141 ms 37504 KB Output is correct
14 Correct 133 ms 35760 KB Output is correct
15 Correct 115 ms 33728 KB Output is correct
16 Correct 89 ms 27116 KB Output is correct
17 Correct 215 ms 37444 KB Output is correct
18 Correct 198 ms 37516 KB Output is correct
19 Correct 169 ms 37484 KB Output is correct
20 Correct 165 ms 37496 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 37580 KB Output is correct
2 Correct 134 ms 37532 KB Output is correct
3 Incorrect 157 ms 38172 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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