oj.uz

Submission #757265

# Submission time Handle Problem Language Result Execution time Memory
757265 2023-06-12T22:15:52 Z shjgkwo Duathlon (APIO18_duathlon) C++17
31 / 100
 297 ms 63060 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;
    }
}

map<int, int> adder[MAXN];

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;
        if (adder[x][y]) continue;
        edge[x].push_back(y);
        edge[y].push_back(x);
        adder[x][y] = 1;
        adder[y][x] = 1;
    }
    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 16756 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16768 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Incorrect 9 ms 16720 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 16756 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16768 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Incorrect 9 ms 16720 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 260 ms 62948 KB Output is correct
2 Correct 253 ms 63060 KB Output is correct
3 Correct 270 ms 57456 KB Output is correct
4 Correct 248 ms 60268 KB Output is correct
5 Correct 241 ms 53792 KB Output is correct
6 Correct 232 ms 54884 KB Output is correct
7 Correct 209 ms 52844 KB Output is correct
8 Correct 237 ms 54216 KB Output is correct
9 Correct 226 ms 51136 KB Output is correct
10 Correct 225 ms 52144 KB Output is correct
11 Correct 176 ms 45024 KB Output is correct
12 Correct 161 ms 44540 KB Output is correct
13 Correct 155 ms 42828 KB Output is correct
14 Correct 168 ms 42288 KB Output is correct
15 Correct 105 ms 37272 KB Output is correct
16 Correct 114 ms 37248 KB Output is correct
17 Correct 14 ms 19156 KB Output is correct
18 Correct 12 ms 19156 KB Output is correct
19 Correct 15 ms 19156 KB Output is correct
20 Correct 11 ms 19156 KB Output is correct
21 Correct 13 ms 19080 KB Output is correct
22 Correct 12 ms 19028 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17108 KB Output is correct
2 Correct 10 ms 17108 KB Output is correct
3 Correct 10 ms 17108 KB Output is correct
4 Correct 9 ms 17176 KB Output is correct
5 Correct 12 ms 17108 KB Output is correct
6 Correct 11 ms 17140 KB Output is correct
7 Correct 11 ms 17108 KB Output is correct
8 Correct 10 ms 17108 KB Output is correct
9 Correct 13 ms 17172 KB Output is correct
10 Correct 10 ms 17140 KB Output is correct
11 Correct 10 ms 17128 KB Output is correct
12 Correct 10 ms 17140 KB Output is correct
13 Correct 9 ms 17080 KB Output is correct
14 Correct 10 ms 17108 KB Output is correct
15 Correct 9 ms 16980 KB Output is correct
16 Correct 9 ms 16960 KB Output is correct
17 Correct 10 ms 17108 KB Output is correct
18 Correct 10 ms 17112 KB Output is correct
19 Correct 10 ms 17108 KB Output is correct
20 Correct 10 ms 17152 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 51648 KB Output is correct
2 Correct 224 ms 51604 KB Output is correct
3 Correct 245 ms 51664 KB Output is correct
4 Correct 219 ms 51576 KB Output is correct
5 Correct 210 ms 51664 KB Output is correct
6 Correct 217 ms 60884 KB Output is correct
7 Correct 239 ms 57844 KB Output is correct
8 Correct 237 ms 56220 KB Output is correct
9 Correct 236 ms 54604 KB Output is correct
10 Correct 203 ms 51736 KB Output is correct
11 Correct 216 ms 51888 KB Output is correct
12 Correct 197 ms 51592 KB Output is correct
13 Correct 243 ms 51676 KB Output is correct
14 Correct 195 ms 48876 KB Output is correct
15 Correct 159 ms 45880 KB Output is correct
16 Correct 105 ms 36552 KB Output is correct
17 Correct 297 ms 51564 KB Output is correct
18 Correct 268 ms 51608 KB Output is correct
19 Correct 272 ms 51524 KB Output is correct
20 Correct 254 ms 51808 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 51692 KB Output is correct
2 Correct 249 ms 51640 KB Output is correct
3 Incorrect 249 ms 53836 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 16756 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16768 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Incorrect 9 ms 16720 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 16756 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16768 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Incorrect 9 ms 16720 KB Output isn't correct
8 Halted 0 ms 0 KB -