oj.uz

Submission #974421

# Submission time Handle Problem Language Result Execution time Memory
974421 2024-05-03T10:14:17 Z efedmrlr Duathlon (APIO18_duathlon) C++17
31 / 100
 112 ms 38228 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  * sbt * (x - sbt); 
            continue;
        }
        int sbt = subsz[c];
        ret += 1ll * 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";
    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 9 ms 22364 KB Output is correct
2 Correct 9 ms 22364 KB Output is correct
3 Correct 10 ms 22616 KB Output is correct
4 Correct 9 ms 22288 KB Output is correct
5 Correct 9 ms 22316 KB Output is correct
6 Correct 11 ms 22364 KB Output is correct
7 Incorrect 9 ms 22360 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22364 KB Output is correct
2 Correct 9 ms 22364 KB Output is correct
3 Correct 10 ms 22616 KB Output is correct
4 Correct 9 ms 22288 KB Output is correct
5 Correct 9 ms 22316 KB Output is correct
6 Correct 11 ms 22364 KB Output is correct
7 Incorrect 9 ms 22360 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 69 ms 38228 KB Output is correct
2 Correct 65 ms 38228 KB Output is correct
3 Correct 81 ms 34824 KB Output is correct
4 Correct 72 ms 36220 KB Output is correct
5 Correct 67 ms 32848 KB Output is correct
6 Correct 73 ms 33364 KB Output is correct
7 Correct 85 ms 32172 KB Output is correct
8 Correct 76 ms 32952 KB Output is correct
9 Correct 71 ms 31316 KB Output is correct
10 Correct 67 ms 31824 KB Output is correct
11 Correct 60 ms 29396 KB Output is correct
12 Correct 55 ms 29392 KB Output is correct
13 Correct 54 ms 29208 KB Output is correct
14 Correct 76 ms 29024 KB Output is correct
15 Correct 52 ms 28360 KB Output is correct
16 Correct 43 ms 28036 KB Output is correct
17 Correct 12 ms 23508 KB Output is correct
18 Correct 12 ms 23508 KB Output is correct
19 Correct 12 ms 23508 KB Output is correct
20 Correct 12 ms 23508 KB Output is correct
21 Correct 12 ms 23440 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 8 ms 22360 KB Output is correct
2 Correct 9 ms 22360 KB Output is correct
3 Correct 9 ms 22364 KB Output is correct
4 Correct 10 ms 22360 KB Output is correct
5 Correct 9 ms 22348 KB Output is correct
6 Correct 10 ms 22364 KB Output is correct
7 Correct 9 ms 22348 KB Output is correct
8 Correct 10 ms 22364 KB Output is correct
9 Correct 8 ms 22364 KB Output is correct
10 Correct 9 ms 22312 KB Output is correct
11 Correct 10 ms 22364 KB Output is correct
12 Correct 9 ms 22364 KB Output is correct
13 Correct 12 ms 22364 KB Output is correct
14 Correct 9 ms 22364 KB Output is correct
15 Correct 9 ms 22360 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 9 ms 22460 KB Output is correct
20 Correct 10 ms 22364 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 32340 KB Output is correct
2 Correct 77 ms 32336 KB Output is correct
3 Correct 100 ms 32340 KB Output is correct
4 Correct 106 ms 32372 KB Output is correct
5 Correct 75 ms 32340 KB Output is correct
6 Correct 112 ms 36784 KB Output is correct
7 Correct 112 ms 35720 KB Output is correct
8 Correct 85 ms 34900 KB Output is correct
9 Correct 80 ms 33872 KB Output is correct
10 Correct 76 ms 32524 KB Output is correct
11 Correct 69 ms 32344 KB Output is correct
12 Correct 95 ms 32332 KB Output is correct
13 Correct 74 ms 32504 KB Output is correct
14 Correct 69 ms 31688 KB Output is correct
15 Correct 65 ms 30936 KB Output is correct
16 Correct 61 ms 28672 KB Output is correct
17 Correct 55 ms 32036 KB Output is correct
18 Correct 50 ms 32056 KB Output is correct
19 Correct 55 ms 32940 KB Output is correct
20 Correct 56 ms 32300 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22364 KB Output is correct
2 Correct 9 ms 22364 KB Output is correct
3 Incorrect 10 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 81 ms 32524 KB Output is correct
2 Correct 98 ms 32336 KB Output is correct
3 Incorrect 90 ms 32080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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