oj.uz

Submission #974338

# Submission time Handle Problem Language Result Execution time Memory
974338 2024-05-03T08:48:11 Z efedmrlr Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 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) {
    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);
    }
    ans += ret;
}

void dfs2(int node, int par, int root) {
    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 << "conn: " << conn << "\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(edg[i][1]);
            cadj[comp[edg[i][1]]].pb(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);
    }
    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 12 ms 22364 KB Output is correct
2 Correct 10 ms 22360 KB Output is correct
3 Correct 8 ms 22364 KB Output is correct
4 Correct 9 ms 22296 KB Output is correct
5 Correct 11 ms 22364 KB Output is correct
6 Correct 8 ms 22364 KB Output is correct
7 Runtime error 739 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22364 KB Output is correct
2 Correct 10 ms 22360 KB Output is correct
3 Correct 8 ms 22364 KB Output is correct
4 Correct 9 ms 22296 KB Output is correct
5 Correct 11 ms 22364 KB Output is correct
6 Correct 8 ms 22364 KB Output is correct
7 Runtime error 739 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 38224 KB Output is correct
2 Correct 107 ms 38088 KB Output is correct
3 Incorrect 95 ms 34824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22360 KB Output is correct
2 Correct 9 ms 22364 KB Output is correct
3 Correct 10 ms 22360 KB Output is correct
4 Correct 10 ms 22360 KB Output is correct
5 Correct 10 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 10 ms 22360 KB Output is correct
9 Correct 10 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 9 ms 22364 KB Output is correct
13 Correct 9 ms 22364 KB Output is correct
14 Correct 9 ms 22364 KB Output is correct
15 Correct 10 ms 22316 KB Output is correct
16 Correct 10 ms 22364 KB Output is correct
17 Correct 11 ms 22452 KB Output is correct
18 Correct 10 ms 22364 KB Output is correct
19 Correct 8 ms 22360 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 76 ms 32336 KB Output is correct
2 Correct 71 ms 32360 KB Output is correct
3 Correct 77 ms 32340 KB Output is correct
4 Correct 80 ms 32536 KB Output is correct
5 Correct 74 ms 32368 KB Output is correct
6 Correct 94 ms 36688 KB Output is correct
7 Correct 96 ms 35828 KB Output is correct
8 Correct 87 ms 34896 KB Output is correct
9 Correct 87 ms 33872 KB Output is correct
10 Correct 82 ms 32340 KB Output is correct
11 Correct 74 ms 32340 KB Output is correct
12 Correct 90 ms 32400 KB Output is correct
13 Correct 96 ms 32352 KB Output is correct
14 Correct 91 ms 31624 KB Output is correct
15 Correct 62 ms 30936 KB Output is correct
16 Correct 47 ms 28412 KB Output is correct
17 Correct 51 ms 32196 KB Output is correct
18 Correct 50 ms 32136 KB Output is correct
19 Correct 56 ms 32940 KB Output is correct
20 Correct 59 ms 32300 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 32336 KB Output is correct
2 Correct 88 ms 32296 KB Output is correct
3 Execution timed out 1094 ms 875416 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22364 KB Output is correct
2 Correct 10 ms 22360 KB Output is correct
3 Correct 8 ms 22364 KB Output is correct
4 Correct 9 ms 22296 KB Output is correct
5 Correct 11 ms 22364 KB Output is correct
6 Correct 8 ms 22364 KB Output is correct
7 Runtime error 739 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22364 KB Output is correct
2 Correct 10 ms 22360 KB Output is correct
3 Correct 8 ms 22364 KB Output is correct
4 Correct 9 ms 22296 KB Output is correct
5 Correct 11 ms 22364 KB Output is correct
6 Correct 8 ms 22364 KB Output is correct
7 Runtime error 739 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -