oj.uz

Submission #974432

# Submission time Handle Problem Language Result Execution time Memory
974432 2024-05-03T10:29:40 Z vjudge1 Duathlon (APIO18_duathlon) C++17
66 / 100
 200 ms 38476 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 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 12 ms 22180 KB Output is correct
6 Correct 10 ms 22360 KB Output is correct
7 Correct 10 ms 22360 KB Output is correct
8 Incorrect 9 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 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 12 ms 22180 KB Output is correct
6 Correct 10 ms 22360 KB Output is correct
7 Correct 10 ms 22360 KB Output is correct
8 Incorrect 9 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 73 ms 38476 KB Output is correct
2 Correct 81 ms 38316 KB Output is correct
3 Correct 77 ms 34368 KB Output is correct
4 Correct 69 ms 36176 KB Output is correct
5 Correct 76 ms 31824 KB Output is correct
6 Correct 73 ms 32592 KB Output is correct
7 Correct 85 ms 31488 KB Output is correct
8 Correct 77 ms 32084 KB Output is correct
9 Correct 70 ms 30492 KB Output is correct
10 Correct 97 ms 30900 KB Output is correct
11 Correct 55 ms 28372 KB Output is correct
12 Correct 66 ms 28420 KB Output is correct
13 Correct 59 ms 28364 KB Output is correct
14 Correct 53 ms 28092 KB Output is correct
15 Correct 50 ms 27576 KB Output is correct
16 Correct 46 ms 27296 KB Output is correct
17 Correct 11 ms 23504 KB Output is correct
18 Correct 17 ms 23508 KB Output is correct
19 Correct 12 ms 23508 KB Output is correct
20 Correct 11 ms 23508 KB Output is correct
21 Correct 12 ms 23508 KB Output is correct
22 Correct 15 ms 23508 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22360 KB Output is correct
2 Correct 9 ms 22364 KB Output is correct
3 Correct 10 ms 22364 KB Output is correct
4 Correct 14 ms 22364 KB Output is correct
5 Correct 9 ms 22364 KB Output is correct
6 Correct 11 ms 22364 KB Output is correct
7 Correct 16 ms 22364 KB Output is correct
8 Correct 13 ms 22364 KB Output is correct
9 Correct 20 ms 22364 KB Output is correct
10 Correct 9 ms 22364 KB Output is correct
11 Correct 10 ms 22364 KB Output is correct
12 Correct 10 ms 22616 KB Output is correct
13 Correct 9 ms 22512 KB Output is correct
14 Correct 10 ms 22364 KB Output is correct
15 Correct 9 ms 22360 KB Output is correct
16 Correct 10 ms 22364 KB Output is correct
17 Correct 10 ms 22388 KB Output is correct
18 Correct 12 ms 22364 KB Output is correct
19 Correct 11 ms 22364 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 172 ms 31268 KB Output is correct
2 Correct 99 ms 31284 KB Output is correct
3 Correct 100 ms 31032 KB Output is correct
4 Correct 178 ms 31060 KB Output is correct
5 Correct 155 ms 31060 KB Output is correct
6 Correct 156 ms 36348 KB Output is correct
7 Correct 200 ms 35168 KB Output is correct
8 Correct 189 ms 34036 KB Output is correct
9 Correct 107 ms 32852 KB Output is correct
10 Correct 113 ms 31060 KB Output is correct
11 Correct 170 ms 31116 KB Output is correct
12 Correct 74 ms 31064 KB Output is correct
13 Correct 103 ms 31028 KB Output is correct
14 Correct 76 ms 30596 KB Output is correct
15 Correct 83 ms 30092 KB Output is correct
16 Correct 45 ms 27876 KB Output is correct
17 Correct 57 ms 30916 KB Output is correct
18 Correct 58 ms 31032 KB Output is correct
19 Correct 98 ms 31740 KB Output is correct
20 Correct 67 ms 31116 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 11 ms 22284 KB Output is correct
3 Correct 11 ms 22360 KB Output is correct
4 Correct 10 ms 22364 KB Output is correct
5 Correct 12 ms 22364 KB Output is correct
6 Correct 10 ms 22364 KB Output is correct
7 Correct 10 ms 22364 KB Output is correct
8 Correct 9 ms 22616 KB Output is correct
9 Correct 11 ms 22364 KB Output is correct
10 Correct 14 ms 22360 KB Output is correct
11 Correct 10 ms 22364 KB Output is correct
12 Correct 14 ms 22364 KB Output is correct
13 Correct 9 ms 22364 KB Output is correct
14 Correct 11 ms 22364 KB Output is correct
15 Correct 9 ms 22364 KB Output is correct
16 Correct 8 ms 22364 KB Output is correct
17 Correct 11 ms 22772 KB Output is correct
18 Correct 10 ms 22364 KB Output is correct
19 Correct 12 ms 22360 KB Output is correct
20 Correct 9 ms 22364 KB Output is correct
21 Correct 13 ms 22364 KB Output is correct
22 Correct 12 ms 22288 KB Output is correct
23 Correct 11 ms 22364 KB Output is correct
24 Correct 11 ms 22476 KB Output is correct
25 Correct 10 ms 22424 KB Output is correct
26 Correct 14 ms 22364 KB Output is correct
27 Correct 11 ms 22364 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 31028 KB Output is correct
2 Correct 123 ms 31100 KB Output is correct
3 Correct 95 ms 30660 KB Output is correct
4 Correct 150 ms 29748 KB Output is correct
5 Correct 72 ms 28732 KB Output is correct
6 Correct 109 ms 28288 KB Output is correct
7 Correct 67 ms 28224 KB Output is correct
8 Correct 62 ms 28104 KB Output is correct
9 Correct 115 ms 27900 KB Output is correct
10 Correct 94 ms 27892 KB Output is correct
11 Correct 154 ms 27624 KB Output is correct
12 Correct 166 ms 27792 KB Output is correct
13 Correct 58 ms 27956 KB Output is correct
14 Correct 63 ms 30452 KB Output is correct
15 Correct 131 ms 34828 KB Output is correct
16 Correct 97 ms 33516 KB Output is correct
17 Correct 94 ms 34132 KB Output is correct
18 Correct 162 ms 33032 KB Output is correct
19 Correct 175 ms 29784 KB Output is correct
20 Correct 173 ms 29800 KB Output is correct
21 Correct 77 ms 30148 KB Output is correct
22 Correct 156 ms 29068 KB Output is correct
23 Correct 64 ms 28488 KB Output is correct
24 Correct 80 ms 30324 KB Output is correct
25 Correct 76 ms 30720 KB Output is correct
26 Correct 102 ms 30056 KB Output is correct
27 Correct 70 ms 30028 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 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 12 ms 22180 KB Output is correct
6 Correct 10 ms 22360 KB Output is correct
7 Correct 10 ms 22360 KB Output is correct
8 Incorrect 9 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 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 12 ms 22180 KB Output is correct
6 Correct 10 ms 22360 KB Output is correct
7 Correct 10 ms 22360 KB Output is correct
8 Incorrect 9 ms 22364 KB Output isn't correct
9 Halted 0 ms 0 KB -