oj.uz

Submission #974431

# Submission time Handle Problem Language Result Execution time Memory
974431 2024-05-03T10:28:48 Z efedmrlr Duathlon (APIO18_duathlon) C++17
66 / 100
 124 ms 38520 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);
    }
    
    // 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 * (cmpsz[comp[node]] - 1) * sbt * (conn - sbt);
    }
    if(cmpsz[comp[node]] < 2) return;
    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 8 ms 22360 KB Output is correct
3 Correct 8 ms 22364 KB Output is correct
4 Correct 9 ms 22364 KB Output is correct
5 Correct 8 ms 22364 KB Output is correct
6 Correct 8 ms 22364 KB Output is correct
7 Correct 8 ms 22364 KB Output is correct
8 Incorrect 10 ms 22364 KB Output isn't correct
9 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 8 ms 22360 KB Output is correct
3 Correct 8 ms 22364 KB Output is correct
4 Correct 9 ms 22364 KB Output is correct
5 Correct 8 ms 22364 KB Output is correct
6 Correct 8 ms 22364 KB Output is correct
7 Correct 8 ms 22364 KB Output is correct
8 Incorrect 10 ms 22364 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 38520 KB Output is correct
2 Correct 79 ms 38520 KB Output is correct
3 Correct 96 ms 34132 KB Output is correct
4 Correct 80 ms 36176 KB Output is correct
5 Correct 86 ms 31824 KB Output is correct
6 Correct 73 ms 32596 KB Output is correct
7 Correct 80 ms 31312 KB Output is correct
8 Correct 78 ms 32080 KB Output is correct
9 Correct 93 ms 30288 KB Output is correct
10 Correct 66 ms 30800 KB Output is correct
11 Correct 53 ms 28520 KB Output is correct
12 Correct 58 ms 28368 KB Output is correct
13 Correct 57 ms 28376 KB Output is correct
14 Correct 53 ms 28108 KB Output is correct
15 Correct 46 ms 27596 KB Output is correct
16 Correct 42 ms 27336 KB Output is correct
17 Correct 14 ms 23508 KB Output is correct
18 Correct 15 ms 23508 KB Output is correct
19 Correct 12 ms 23516 KB Output is correct
20 Correct 11 ms 23508 KB Output is correct
21 Correct 12 ms 23508 KB Output is correct
22 Correct 12 ms 23508 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22364 KB Output is correct
2 Correct 9 ms 22396 KB Output is correct
3 Correct 11 ms 22364 KB Output is correct
4 Correct 11 ms 22432 KB Output is correct
5 Correct 10 ms 22348 KB Output is correct
6 Correct 9 ms 22364 KB Output is correct
7 Correct 9 ms 22364 KB Output is correct
8 Correct 10 ms 22364 KB Output is correct
9 Correct 11 ms 22420 KB Output is correct
10 Correct 10 ms 22360 KB Output is correct
11 Correct 9 ms 22364 KB Output is correct
12 Correct 9 ms 22364 KB Output is correct
13 Correct 10 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 10 ms 22364 KB Output is correct
17 Correct 10 ms 22400 KB Output is correct
18 Correct 10 ms 22364 KB Output is correct
19 Correct 12 ms 22456 KB Output is correct
20 Correct 9 ms 22616 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 31056 KB Output is correct
2 Correct 72 ms 31064 KB Output is correct
3 Correct 76 ms 31056 KB Output is correct
4 Correct 80 ms 31284 KB Output is correct
5 Correct 91 ms 31120 KB Output is correct
6 Correct 107 ms 36244 KB Output is correct
7 Correct 124 ms 35128 KB Output is correct
8 Correct 91 ms 33876 KB Output is correct
9 Correct 85 ms 33016 KB Output is correct
10 Correct 84 ms 31468 KB Output is correct
11 Correct 78 ms 31092 KB Output is correct
12 Correct 88 ms 31100 KB Output is correct
13 Correct 75 ms 31136 KB Output is correct
14 Correct 91 ms 30544 KB Output is correct
15 Correct 70 ms 29912 KB Output is correct
16 Correct 42 ms 27780 KB Output is correct
17 Correct 54 ms 30968 KB Output is correct
18 Correct 55 ms 30780 KB Output is correct
19 Correct 57 ms 31664 KB Output is correct
20 Correct 57 ms 31156 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22364 KB Output is correct
2 Correct 10 ms 22428 KB Output is correct
3 Correct 10 ms 22364 KB Output is correct
4 Correct 8 ms 22404 KB Output is correct
5 Correct 10 ms 22364 KB Output is correct
6 Correct 9 ms 22356 KB Output is correct
7 Correct 9 ms 22360 KB Output is correct
8 Correct 10 ms 22364 KB Output is correct
9 Correct 9 ms 22364 KB Output is correct
10 Correct 12 ms 22628 KB Output is correct
11 Correct 9 ms 22364 KB Output is correct
12 Correct 11 ms 22432 KB Output is correct
13 Correct 9 ms 22364 KB Output is correct
14 Correct 11 ms 22360 KB Output is correct
15 Correct 10 ms 22364 KB Output is correct
16 Correct 9 ms 22504 KB Output is correct
17 Correct 10 ms 22364 KB Output is correct
18 Correct 9 ms 22364 KB Output is correct
19 Correct 9 ms 22364 KB Output is correct
20 Correct 12 ms 22364 KB Output is correct
21 Correct 10 ms 22284 KB Output is correct
22 Correct 10 ms 22364 KB Output is correct
23 Correct 10 ms 22360 KB Output is correct
24 Correct 8 ms 22364 KB Output is correct
25 Correct 10 ms 22396 KB Output is correct
26 Correct 11 ms 22360 KB Output is correct
27 Correct 10 ms 22364 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 31276 KB Output is correct
2 Correct 112 ms 31312 KB Output is correct
3 Correct 98 ms 30440 KB Output is correct
4 Correct 82 ms 31268 KB Output is correct
5 Correct 67 ms 30288 KB Output is correct
6 Correct 80 ms 29780 KB Output is correct
7 Correct 68 ms 29436 KB Output is correct
8 Correct 56 ms 29352 KB Output is correct
9 Correct 56 ms 29268 KB Output is correct
10 Correct 63 ms 29008 KB Output is correct
11 Correct 66 ms 29012 KB Output is correct
12 Correct 59 ms 29020 KB Output is correct
13 Correct 55 ms 29268 KB Output is correct
14 Correct 62 ms 31572 KB Output is correct
15 Correct 99 ms 36332 KB Output is correct
16 Correct 117 ms 35100 KB Output is correct
17 Correct 117 ms 35988 KB Output is correct
18 Correct 82 ms 34388 KB Output is correct
19 Correct 98 ms 31312 KB Output is correct
20 Correct 74 ms 31272 KB Output is correct
21 Correct 70 ms 31344 KB Output is correct
22 Correct 66 ms 30544 KB Output is correct
23 Correct 73 ms 29824 KB Output is correct
24 Correct 67 ms 31808 KB Output is correct
25 Correct 68 ms 32132 KB Output is correct
26 Correct 77 ms 31432 KB Output is correct
27 Correct 66 ms 31356 KB Output is correct

Subtask #8
0 / 8.0

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