oj.uz

Submission #742894

# Submission time Handle Problem Language Result Execution time Memory
742894 2023-05-17T05:45:40 Z PixelCat Duathlon (APIO18_duathlon) C++14
31 / 100
 148 ms 33160 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 = 100010;

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

vector<int> bcc[MAXN * 2];
int siz[MAXN * 2];
int sum[MAXN * 2];
int ban[MAXN * 2];
int cur_bcc = 0;

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) {
    sum[n] = siz[n] = (n <= N);
    for(auto &i:bcc[n]) if(i != p) {
        dfs_siz(i, n, N);
        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(sum[k] > sum[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]) {
            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);
        dfs_ban(i, i, n, sum[i]);
        dfs_ans(i, i, n, sum[i]);
    }
    cout << ans << "\n";

    // For(i, 1, n) cout << ban[i] << " \n"[i == n];
    // 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 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Incorrect 4 ms 7380 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Incorrect 4 ms 7380 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 71 ms 29760 KB Output is correct
2 Correct 97 ms 29700 KB Output is correct
3 Correct 88 ms 28684 KB Output is correct
4 Correct 81 ms 28484 KB Output is correct
5 Correct 79 ms 25480 KB Output is correct
6 Correct 95 ms 27552 KB Output is correct
7 Correct 92 ms 25532 KB Output is correct
8 Correct 113 ms 26084 KB Output is correct
9 Correct 94 ms 23996 KB Output is correct
10 Correct 103 ms 24264 KB Output is correct
11 Correct 72 ms 21732 KB Output is correct
12 Correct 74 ms 21456 KB Output is correct
13 Correct 63 ms 21564 KB Output is correct
14 Correct 69 ms 21192 KB Output is correct
15 Correct 49 ms 19768 KB Output is correct
16 Correct 50 ms 19564 KB Output is correct
17 Correct 8 ms 12120 KB Output is correct
18 Correct 8 ms 12116 KB Output is correct
19 Correct 8 ms 11988 KB Output is correct
20 Correct 9 ms 12040 KB Output is correct
21 Correct 8 ms 11856 KB Output is correct
22 Correct 11 ms 11860 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7512 KB Output is correct
2 Correct 5 ms 7508 KB Output is correct
3 Correct 7 ms 7508 KB Output is correct
4 Correct 7 ms 7636 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 4 ms 7636 KB Output is correct
7 Correct 4 ms 7636 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 5 ms 7508 KB Output is correct
10 Correct 5 ms 7516 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 5 ms 7524 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 5 ms 7480 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct
16 Correct 4 ms 7508 KB Output is correct
17 Correct 5 ms 7512 KB Output is correct
18 Correct 4 ms 7516 KB Output is correct
19 Correct 5 ms 7540 KB Output is correct
20 Correct 5 ms 7516 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 25500 KB Output is correct
2 Correct 109 ms 25384 KB Output is correct
3 Correct 109 ms 25560 KB Output is correct
4 Correct 105 ms 25420 KB Output is correct
5 Correct 100 ms 25476 KB Output is correct
6 Correct 121 ms 33160 KB Output is correct
7 Correct 116 ms 31020 KB Output is correct
8 Correct 148 ms 29512 KB Output is correct
9 Correct 121 ms 28076 KB Output is correct
10 Correct 100 ms 25476 KB Output is correct
11 Correct 95 ms 25376 KB Output is correct
12 Correct 108 ms 25468 KB Output is correct
13 Correct 95 ms 25400 KB Output is correct
14 Correct 85 ms 24472 KB Output is correct
15 Correct 75 ms 23352 KB Output is correct
16 Correct 47 ms 19780 KB Output is correct
17 Correct 65 ms 25772 KB Output is correct
18 Correct 65 ms 25852 KB Output is correct
19 Correct 69 ms 26116 KB Output is correct
20 Correct 71 ms 25836 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 25464 KB Output is correct
2 Correct 110 ms 25288 KB Output is correct
3 Incorrect 135 ms 24820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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