oj.uz

Submission #742922

# Submission time Handle Problem Language Result Execution time Memory
742922 2023-05-17T06:10:24 Z PixelCat Duathlon (APIO18_duathlon) C++14
31 / 100
 145 ms 36372 KB 
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200010;

vector<int> adj[MAXN];
int dep[MAXN];
int lo[MAXN];
int id[MAXN];

vector<int> bcc[MAXN];
int siz[MAXN];
int sum[MAXN];
int ban[MAXN];
int cur_bcc;

vector<int> st;
void dfs_bcc(int n, int p, int d) {
    dep[n] = lo[n] = d;
    st.eb(n);
    for(auto &i:adj[n]) if(i != p) {
        if(dep[i]) {
            lo[n] = min(lo[n], dep[i]);
        } else {
            dfs_bcc(i, n, d + 1);
            lo[n] = min(lo[n], lo[i]);
            if(lo[i] >= dep[n]) {
                // bcc found
                cur_bcc++;
                int last = 0;
                while(last != n) {
                    last = st.back(); st.pop_back();
                    bcc[last].eb(cur_bcc);
                    bcc[cur_bcc].eb(last);
                }
                st.eb(n);
            }
        }
    }
}

void dfs_siz(int n, int p, int N, int d) {
    dep[n] = d;
    sum[n] = siz[n] = (n <= N);
    for(auto &i:bcc[n]) if(i != p) {
        dfs_siz(i, n, N, d + 1);
        sum[n] += sum[i];
    }
}

#define C(x) ((x) * ((x) - 1))
void dfs_ban(int n, int p, int N, int tot) {
    auto size = [&](int r, int k) {
        if(dep[k] < dep[r]) return tot - sum[r];
        return sum[k];
    };
    for(auto &i:bcc[n]) if(i != p) {
        dfs_ban(i, n, N, tot);
    }
    if(n > N) {
        for(auto &i:bcc[n]) {
            // cout << n << " " << i << " " << size(n, i) << " " << tot - sum[n] << " " << sum[i] << "\n";
            ban[n] += C(size(n, i));
            ban[i] -= C(size(n, i));
        }
        for(auto &i:bcc[n]) {
            ban[i] += ban[n];
        }
    }
}

int ans = 0;
void dfs_ans(int n, int p, int N, int tot) {
    if(n <= N) ans += C(tot - 1) - ban[n];
    for(auto &i:bcc[n]) if(i != p) dfs_ans(i, n, N, tot);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^= nya
    int n, m; cin >> n >> m;
    while(m--) {
        int a, b; cin >> a >> b;
        adj[a].eb(b);
        adj[b].eb(a);
    }
    cur_bcc = n;
    For(i, 1, n) if(!dep[i]) {
        dfs_bcc(i, i, 1);
        dfs_siz(i, i, n, 1);
        // cout << i << " " << sum[i] << "\n";
        dfs_ban(i, i, n, sum[i]);
        dfs_ans(i, i, n, sum[i]);
    }
    cout << ans << "\n";

    // For(i, 1, cur_bcc) cout << dep[i] << " \n"[i == cur_bcc];
    // For(i, 1, cur_bcc) cout << ban[i] << " \n"[i == cur_bcc];
    // For(i, 1, cur_bcc) {
    //     cout << i << ":";
    //     for(auto &j:bcc[i]) cout << " " << j;
    //     cout << "\n";
    // }
    return 0;
}

/*

4 3
1 2
2 3
3 4
= 8

4 4
1 2
2 3
3 4
4 2
= 14

5 5
1 2
2 3
3 1
3 4
3 5
= 24

5 6
1 2
2 3
3 1
1 4
4 5
5 1
= 36

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 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 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 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 30864 KB Output is correct
2 Correct 77 ms 30832 KB Output is correct
3 Correct 118 ms 30224 KB Output is correct
4 Correct 90 ms 31116 KB Output is correct
5 Correct 88 ms 28100 KB Output is correct
6 Correct 96 ms 30380 KB Output is correct
7 Correct 106 ms 28428 KB Output is correct
8 Correct 99 ms 28892 KB Output is correct
9 Correct 99 ms 26820 KB Output is correct
10 Correct 97 ms 26984 KB Output is correct
11 Correct 74 ms 24392 KB Output is correct
12 Correct 78 ms 24132 KB Output is correct
13 Correct 67 ms 24264 KB Output is correct
14 Correct 69 ms 23884 KB Output is correct
15 Correct 58 ms 22496 KB Output is correct
16 Correct 56 ms 22180 KB Output is correct
17 Correct 10 ms 14424 KB Output is correct
18 Correct 11 ms 14548 KB Output is correct
19 Correct 10 ms 14440 KB Output is correct
20 Correct 10 ms 14336 KB Output is correct
21 Correct 10 ms 14276 KB Output is correct
22 Correct 12 ms 14340 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 9884 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9940 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 6 ms 9940 KB Output is correct
18 Correct 5 ms 9812 KB Output is correct
19 Correct 6 ms 9928 KB Output is correct
20 Correct 5 ms 9940 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 27292 KB Output is correct
2 Correct 105 ms 28528 KB Output is correct
3 Correct 139 ms 28588 KB Output is correct
4 Correct 120 ms 28572 KB Output is correct
5 Correct 102 ms 28536 KB Output is correct
6 Correct 126 ms 36372 KB Output is correct
7 Correct 145 ms 34168 KB Output is correct
8 Correct 138 ms 32624 KB Output is correct
9 Correct 123 ms 31240 KB Output is correct
10 Correct 110 ms 28532 KB Output is correct
11 Correct 124 ms 28568 KB Output is correct
12 Correct 97 ms 28612 KB Output is correct
13 Correct 99 ms 28552 KB Output is correct
14 Correct 90 ms 27432 KB Output is correct
15 Correct 84 ms 26312 KB Output is correct
16 Correct 55 ms 22532 KB Output is correct
17 Correct 79 ms 28940 KB Output is correct
18 Correct 92 ms 28968 KB Output is correct
19 Correct 72 ms 29272 KB Output is correct
20 Correct 91 ms 28988 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 27296 KB Output is correct
2 Correct 106 ms 28384 KB Output is correct
3 Incorrect 113 ms 27776 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 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 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -