oj.uz

Submission #974427

# Submission time Handle Problem Language Result Execution time Memory
974427 2024-05-03T10:25:55 Z efedmrlr Duathlon (APIO18_duathlon) C++17
31 / 100
 123 ms 37004 KB 
#include <bits/stdc++.h>

#define int long long int
#define lli int
#define ld long double
#define pb push_back
#define MP make_pair
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 2e5 + 5;
const int INF = 1e9 + 500;
int n, m;
vector<vector<array<int, 2> > > adj(N, vector<array<int, 2> >());
int tim = 0;
vector<int> tin(N, -1), low(N, 0);
vector<array<int, 2> > edg(N);
vector<bool> isBr(N, 0);
vector<int> comp(N, -1), cmpsz(N, 0);
vector<vector<int> > cadj(N, vector<int>());
vector<int> subsz(N, 0);
vector<int> rt;
vector<int> vis(N, 0);
lli ans = 0;
void find_bridge(int node, int par) {
    tin[node] = low[node] = tim++;
    for(auto c : adj[node]) {
        if(c[0] == par) {
            continue;
        }
        if(tin[c[0]] != -1) {
            low[node] = min(low[node], tin[c[0]]);
        }
        else {
            find_bridge(c[0], node);
            low[node] = min(low[node], low[c[0]]);
            // cout << "c[1]:"  << c[1] << " node:" << node << " lowc0:" << low[c[0]] << " tin[node]:" << tin[node] << "\n";
            if(low[c[0]] > tin[node]) {
                //bridge
                isBr[c[1]] = 1;
            }
        }
    }
}

void get_comp(int node, int cm) {
    comp[node] = cm;
    cmpsz[cm]++;
    for(auto c : adj[node]) {
        if(comp[c[0]] != -1 || isBr[c[1]]) continue;
        get_comp(c[0], cm);
    }
}

void prec(int node, int par) {
    subsz[node] = cmpsz[node];
    for(auto c : cadj[node]) {
        if(c == par) continue;
        prec(c, node);
        subsz[node] += subsz[c];
    }
}

void dfs(int node, int par, int root) {
    // cout << "node:" << node << "\n";
    lli ret = 0;
    lli x = subsz[root] - cmpsz[node];
    for(auto c : cadj[node]) {
        if(c == par) {
            int sbt = subsz[root] - subsz[node];
            ret += 1ll * cmpsz[node] * sbt * (x - sbt); 
            continue;
        }
        int sbt = subsz[c];
        ret += 1ll * cmpsz[node] * sbt * (x - sbt);
        dfs(c, node, root);
    }
    // cout << "node: " << node << " ret:" << ret << "\n";
    ans += ret;
}

void dfs2(int node, int par, int root) {
    // cout << "node:" << node << "\n";
    int conn = 0;
    vis[node] = 1;
    for(auto c : adj[node]) {
        if(!isBr[c[1]]) {
            if(vis[c[0]]) continue;
            dfs2(c[0], node, root);
            continue;
        }
        if(c[0] == par) {
            conn += subsz[root] - subsz[comp[node]];
            continue;
        }    
        conn += subsz[comp[c[0]]];
        dfs2(c[0], node, root);
    }
    if(cmpsz[comp[node]] < 2) return;
    // cout << "node:" << node << "conn: " << conn << "\n";
    // cout << "add : " << 2ll * (cmpsz[comp[node]] - 1) * (subsz[root] - conn - cmpsz[comp[node]]) << "\n";

    for(auto c : adj[node]) {
        if(!isBr[c[1]]) continue;
        int sbt;
        if(c[0] == par) {
            sbt = subsz[root] - subsz[comp[node]];
        }
        else {
            sbt = subsz[comp[c[0]]];
        }
        ans -= 1ll * (comp[node] - 1) * sbt * (conn - sbt);
    }

    ans += 2ll * (cmpsz[comp[node]] - 1) * (subsz[root] - conn - cmpsz[comp[node]]);
}

void solve() {
    cin >> n >> m;
    REP(i, m) {
        int u, v;
        cin >> u >> v;
        edg[i] = {u, v};
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }    
    for(int i = 1; i <= n; i++) {
        if(tin[i] != -1) continue;
        rt.pb(i);
        find_bridge(i, 0);
    }
    int cur = 1;
    for(int i = 1; i <= n; i++) {
        if(comp[i] == -1) {
            get_comp(i, cur++);
        }
        // cout << "i:" << i << " comp:" << comp[i] << "\n";
    }
    for(int i = 0; i < m; i++) {
        if(isBr[i]) {
            // cout << edg[i][0] << " " << edg[i][1] << endl;
            cadj[comp[edg[i][0]]].pb(comp[edg[i][1]]);
            cadj[comp[edg[i][1]]].pb(comp[edg[i][0]]);
        }
    }
    for(auto c : rt) {
        prec(comp[c], 0);
    }
    for(int i = 1; i < cur; i++) {
        ans += 1ll * cmpsz[i] * (cmpsz[i] - 1) * (cmpsz[i] - 2);
    }
    // cout << "ans: " << ans << "\n";
    for(int c : rt) {
        dfs(comp[c], 0, comp[c]);
    }
    // cout << "ans:" << ans << "\n";
    for(int c : rt) {
        dfs2(c, 0, comp[c]);
    }

    cout << ans << "\n";
}


signed main() {
    fastio();
    solve();
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22360 KB Output is correct
2 Correct 10 ms 22364 KB Output is correct
3 Correct 9 ms 22364 KB Output is correct
4 Correct 9 ms 22364 KB Output is correct
5 Correct 9 ms 22364 KB Output is correct
6 Correct 8 ms 22168 KB Output is correct
7 Incorrect 7 ms 22264 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 74 ms 37004 KB Output is correct
2 Correct 70 ms 36836 KB Output is correct
3 Correct 95 ms 33356 KB Output is correct
4 Correct 67 ms 35096 KB Output is correct
5 Correct 76 ms 31584 KB Output is correct
6 Correct 78 ms 32040 KB Output is correct
7 Correct 67 ms 30992 KB Output is correct
8 Correct 98 ms 31600 KB Output is correct
9 Correct 67 ms 29944 KB Output is correct
10 Correct 66 ms 30544 KB Output is correct
11 Correct 55 ms 28388 KB Output is correct
12 Correct 62 ms 28364 KB Output is correct
13 Correct 56 ms 28364 KB Output is correct
14 Correct 59 ms 28096 KB Output is correct
15 Correct 52 ms 27692 KB Output is correct
16 Correct 56 ms 27420 KB Output is correct
17 Correct 11 ms 23508 KB Output is correct
18 Correct 13 ms 23508 KB Output is correct
19 Correct 12 ms 23508 KB Output is correct
20 Correct 14 ms 23344 KB Output is correct
21 Correct 13 ms 23508 KB Output is correct
22 Correct 13 ms 23508 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 31200 KB Output is correct
2 Correct 85 ms 31056 KB Output is correct
3 Correct 77 ms 31060 KB Output is correct
4 Correct 79 ms 31056 KB Output is correct
5 Correct 74 ms 31056 KB Output is correct
6 Correct 123 ms 35584 KB Output is correct
7 Correct 86 ms 34456 KB Output is correct
8 Correct 87 ms 33620 KB Output is correct
9 Correct 94 ms 32596 KB Output is correct
10 Correct 88 ms 31056 KB Output is correct
11 Correct 76 ms 31276 KB Output is correct
12 Correct 81 ms 31060 KB Output is correct
13 Correct 73 ms 31060 KB Output is correct
14 Correct 66 ms 30548 KB Output is correct
15 Correct 61 ms 29920 KB Output is correct
16 Correct 51 ms 28200 KB Output is correct
17 Correct 53 ms 30916 KB Output is correct
18 Correct 56 ms 31044 KB Output is correct
19 Correct 52 ms 31660 KB Output is correct
20 Correct 51 ms 31024 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 31040 KB Output is correct
2 Correct 75 ms 31060 KB Output is correct
3 Incorrect 81 ms 30804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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