oj.uz

Submission #967272

# Submission time Handle Problem Language Result Execution time Memory
967272 2024-04-21T16:50:28 Z steveonalex Duathlon (APIO18_duathlon) C++17
31 / 100
 237 ms 55352 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 1e5 + 69;
int n, m;
vector<int> graph[N];

int num[N], low[N];
bool isJoint[N];
vector<int> st;
int dfs_cnt;
vector<vector<int>> bbc;

void dfs(int u, int p){
    num[u] = low[u] = ++dfs_cnt;
    st.push_back(u);

    vector<int> child;
    for(int v: graph[u]) {
        if (v == p) {p = -1; continue;}
        if (num[v]){
            minimize(low[u], num[v]);
        }
        else{
            child.push_back(v);
            dfs(v, u);
            minimize(low[u], low[v]);
            if (low[v] >= num[u]){
                isJoint[u] = true;
            }
        }
    }
    if (u == p) isJoint[u] = isJoint[u] && (child.size() >= 2);
    if (!isJoint[u]) return;
    while(child.size()){
        int v = child.back();
        child.pop_back();

        bbc.push_back({});
        while(bbc.back().empty() || bbc.back().back() != v){
            bbc.back().push_back(st.back());
            st.pop_back();
        }
        bbc.back().push_back(u);
    }
}

vector<int> bc_tree[2*N];
int joint_cnt = 0;
int pos[2*N];
int sz[2 * N];

int generate_block_cut_tree(){
    dfs_cnt = 0;
    for(int i= 1; i<=n; ++i) if (num[i] == 0){
        dfs(i, i);
        if (st.size()) {
            bbc.push_back(st);
            st.clear();
        }
    }

    int idx = 0;
    for(int i= 1; i<=n; ++i){
        if (!isJoint[i]) continue;
        joint_cnt++;
        pos[i] = ++idx;
        sz[idx] = 1;
    }

    for(vector<int> i: bbc){
        ++idx;
        sz[idx] = i.size();
        for(int j: i){
            if (isJoint[j]){
                int u = idx, v = pos[j];
                sz[v]--;
                bc_tree[u].push_back(v);
                bc_tree[v].push_back(u);
            }
        }
    }
    return idx;
}

bool visited[N * 2];
int og[N * 2];
ll ans = 0;

void get_sz(int u, int p){
    visited[u] = 1;
    og[u] = sz[u];
    for(int v: bc_tree[u]) if (v != p){
        get_sz(v, u);
        sz[u] += sz[v];
    }
}

void dfs(int u, int p, int source){
    if (u <= joint_cnt){
        vector<pair<int, int>> child;
        for(int v: bc_tree[u]){
            if (v != p) child.push_back({sz[v] - 1, v});
            else child.push_back({sz[source] - sz[u] - 1, v});
        }
        int sum = 0;
        for(pair<int, int> i: child) {
            sum += i.first;
        }

        // sum -= child.back();
        // child.pop_back();
        // child.push_back(sz[source] - sz[u] - 1);
        // sum += child.back();
        for(pair<int, int> i: child){
            ans -= 1LL * (og[i.second] - 1) * (sum - i.first) * (sum - i.first - 1);
            ans -= 2LL * (og[i.second] - 1) * (sum - i.first);
        }
    }

    for(int v: bc_tree[u]) if (v != p){
        dfs(v, u, source);
    }
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    // if (m != n - 1) return -1;
    for(int i= 0; i<m; ++i){
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    int tree_sz = generate_block_cut_tree();

    for(int i= joint_cnt + 1; i<=tree_sz; ++i) if (!visited[i]){
        get_sz(i, i);
        int M = sz[i];
        cerr << M << "\n";
        ans += 1LL * M * (M - 1) * (M - 2);
        dfs(i, i, i);
    }  

    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Incorrect 2 ms 10732 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 46 ms 32460 KB Output is correct
2 Correct 51 ms 32460 KB Output is correct
3 Correct 74 ms 35176 KB Output is correct
4 Correct 52 ms 29864 KB Output is correct
5 Correct 56 ms 28800 KB Output is correct
6 Correct 66 ms 37696 KB Output is correct
7 Correct 61 ms 28100 KB Output is correct
8 Correct 64 ms 32708 KB Output is correct
9 Correct 62 ms 25328 KB Output is correct
10 Correct 64 ms 26068 KB Output is correct
11 Correct 127 ms 20512 KB Output is correct
12 Correct 94 ms 20272 KB Output is correct
13 Correct 109 ms 19512 KB Output is correct
14 Correct 116 ms 19608 KB Output is correct
15 Correct 141 ms 18696 KB Output is correct
16 Correct 135 ms 18420 KB Output is correct
17 Correct 224 ms 17020 KB Output is correct
18 Correct 224 ms 16636 KB Output is correct
19 Correct 224 ms 16524 KB Output is correct
20 Correct 225 ms 16564 KB Output is correct
21 Correct 237 ms 17408 KB Output is correct
22 Correct 224 ms 16376 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 25348 KB Output is correct
2 Correct 65 ms 25596 KB Output is correct
3 Correct 63 ms 25608 KB Output is correct
4 Correct 62 ms 26112 KB Output is correct
5 Correct 75 ms 26204 KB Output is correct
6 Correct 98 ms 55352 KB Output is correct
7 Correct 93 ms 36532 KB Output is correct
8 Correct 79 ms 33924 KB Output is correct
9 Correct 73 ms 31152 KB Output is correct
10 Correct 66 ms 26364 KB Output is correct
11 Correct 62 ms 25536 KB Output is correct
12 Correct 62 ms 25756 KB Output is correct
13 Correct 69 ms 26064 KB Output is correct
14 Correct 87 ms 25344 KB Output is correct
15 Correct 94 ms 23824 KB Output is correct
16 Correct 139 ms 20480 KB Output is correct
17 Correct 43 ms 27628 KB Output is correct
18 Correct 41 ms 25892 KB Output is correct
19 Correct 43 ms 26164 KB Output is correct
20 Correct 44 ms 25880 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 25312 KB Output is correct
2 Correct 70 ms 26116 KB Output is correct
3 Incorrect 71 ms 24828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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