oj.uz

Submission #742865

# Submission time Handle Problem Language Result Execution time Memory
742865 2023-05-17T04:49:06 Z PixelCat Duathlon (APIO18_duathlon) C++14
31 / 100
 88 ms 22892 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];
vector<int> bcc[MAXN];
int par[MAXN];
int dep[MAXN];
int id[MAXN];
int siz[MAXN];
int sum[MAXN];
int cur_bcc = 0;

void dfs_bcc(int n, int p, int d) {
    par[n] = p;
    dep[n] = d;
    for(auto &i:adj[n]) if(i != p) {
        if(!par[i]) {
            // tree edge
            dfs_bcc(i, n, d + 1);
        } else if(dep[i] < dep[n]) {
            // back edge
            cur_bcc++;
            int t = n;
            while(true) {
                id[t] = cur_bcc;
                if(t == i) break;
                t = par[t];
            }
        }
    }
    if(!id[n]) id[n] = ++cur_bcc;
    for(auto &i:adj[n]) if(dep[i] > dep[n] && id[i] != id[n]) {
        bcc[id[i]].eb(id[n]);
        bcc[id[n]].eb(id[i]);
    }
    siz[id[n]]++;
}

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

int ans;
#define C(x) ((x) * ((x) - 1))
void dfs_ans(int n, int p, int tot_n) {
    int t = C(tot_n - 1) * siz[n];
    for(auto &i:bcc[n]) {
        int s = sum[i];
        if(i == p) s = tot_n - sum[n];
        t -= C(s + 1) * (siz[n] - 1) + C(s);

        if(i != p) dfs_ans(i, n, tot_n);
    }
    ans += t;
}

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);
    }
    ans = 0;
    For(i, 1, n) if(!par[i]) {
        For(j, 1, cur_bcc) {
            bcc[j].clear();
            siz[j] = 0;
        }
        cur_bcc = 0;
        dfs_bcc(i, i, 1);
        dfs_siz(1, 1);
        dfs_ans(1, 1, sum[1]);

        // cout << cur_bcc << "\n";
        // For(j, 1, cur_bcc) {
        //     cout << j << " = " << siz[j] << ", " << sum[j] << ":";
        //     for(auto &k:bcc[j]) cout << " " << k;
        //     cout << "\n";
        // }
        // cout << flush;
    }
    cout << ans << "\n";
    return 0;
}

/*

4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 19884 KB Output is correct
2 Correct 70 ms 19844 KB Output is correct
3 Correct 71 ms 17484 KB Output is correct
4 Correct 61 ms 19444 KB Output is correct
5 Correct 73 ms 15936 KB Output is correct
6 Correct 65 ms 18196 KB Output is correct
7 Correct 59 ms 13960 KB Output is correct
8 Correct 77 ms 15648 KB Output is correct
9 Correct 64 ms 12648 KB Output is correct
10 Correct 59 ms 13736 KB Output is correct
11 Correct 44 ms 11220 KB Output is correct
12 Correct 46 ms 11084 KB Output is correct
13 Correct 54 ms 11116 KB Output is correct
14 Correct 40 ms 11040 KB Output is correct
15 Correct 29 ms 10608 KB Output is correct
16 Correct 33 ms 10496 KB Output is correct
17 Correct 5 ms 7332 KB Output is correct
18 Correct 6 ms 7380 KB Output is correct
19 Correct 5 ms 7380 KB Output is correct
20 Correct 5 ms 7296 KB Output is correct
21 Correct 6 ms 7328 KB Output is correct
22 Correct 6 ms 7336 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 16332 KB Output is correct
2 Correct 85 ms 16308 KB Output is correct
3 Correct 72 ms 16304 KB Output is correct
4 Correct 88 ms 16300 KB Output is correct
5 Correct 71 ms 16352 KB Output is correct
6 Correct 71 ms 22892 KB Output is correct
7 Correct 73 ms 19428 KB Output is correct
8 Correct 75 ms 18472 KB Output is correct
9 Correct 73 ms 17720 KB Output is correct
10 Correct 60 ms 14440 KB Output is correct
11 Correct 65 ms 15816 KB Output is correct
12 Correct 66 ms 13104 KB Output is correct
13 Correct 73 ms 12688 KB Output is correct
14 Correct 44 ms 10828 KB Output is correct
15 Correct 47 ms 10580 KB Output is correct
16 Correct 27 ms 9676 KB Output is correct
17 Correct 40 ms 16672 KB Output is correct
18 Correct 44 ms 16664 KB Output is correct
19 Correct 47 ms 16936 KB Output is correct
20 Correct 43 ms 16708 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 16364 KB Output is correct
2 Correct 68 ms 16040 KB Output is correct
3 Incorrect 69 ms 14560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -