oj.uz

Submission #901635

# Submission time Handle Problem Language Result Execution time Memory
901635 2024-01-09T18:51:06 Z SalihSahin Duathlon (APIO18_duathlon) C++17
31 / 100
 117 ms 47956 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
using namespace std;
 
const int mod = 1e9 + 7;
const int inf = 1e17*2;
const int N = 2e5 + 5;

vector<int> adj[N], low(N), in(N), vis(N), par(N), sz(N), sub(N), cl(N), clsz(N);
int timer = 0;
vector<pair<int, int> > bridge;

void dfs(int node, int par, int &cal, int &cnt){
    vis[node] = 1;
    in[node] = low[node] = timer++;
    cl[node] = cal;
    cnt++;

    for(auto itr: adj[node]){
        if(itr == par) continue;
        if(vis[itr]){
            low[node] = min(low[node], in[itr]);
        }
        else{
            dfs(itr, node, cal, cnt);
            low[node] = min(low[node], low[itr]);
            if(in[node] < low[itr]){
                bridge.pb(mp(min(node, itr), max(node, itr)));
            }
        }
    }
}

int find(int a){
    if(a == par[a]) return a;
    return par[a] = find(par[a]);
}

void merge(int a, int b){
    par[find(b)] = find(a);
}

vector<int> adj2[N];

void dfs2(int node, int &cnt){
    cnt++;
    vis[node] = 1;

    for(auto itr: adj2[node]){
        if(!vis[itr]){
            dfs2(itr, cnt);
            merge(node, itr);
        }
    }
}

vector<int> adjb[N];

void subcalc(int node, int par){
    vis[node] = 1;

    for(auto itr: adjb[node]){
        if(itr != par){
            subcalc(itr, node);
            sub[node] += sub[itr];
        }
    }
    sub[node] += sz[node];
}

void dfs3(int node, int par, int total, int &ans){
    vis[node] = 1;

    vector<int> v;
    for(auto itr: adjb[node]){
        if(itr != par) v.pb(sub[itr]); 
    }
    if(node != par) v.pb(total - sub[node]);

    for(auto itr: v){
        ans += sz[node] * itr * (total - sz[node] - itr);
    }

    for(auto itr: adjb[node]){
        if(itr != par){
            dfs3(itr, node, total, ans);
        }
    }
}

void dfs4(int node, int par, int &val){
    val += sz[node];
    for(auto itr: adjb[node]){
        if(itr == par) continue;
        dfs4(itr, node, val);
    }
}

int32_t main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int n, m;
    cin>>n>>m;

    vector<pair<int, int> > edge(m);
    for(int i = 0; i < m; i++){
        int u, v;
        cin>>u>>v;
        if(u > v) swap(u, v);
        edge[i] = mp(u, v);
        adj[u].pb(v);
        adj[v].pb(u);
    }

    int calss = 0;
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        calss++;
        int cnto = 0;
        dfs(i, i, calss, cnto);
        clsz[calss] = cnto;

    }
    sort(bridge.begin(), bridge.end());
    sort(edge.begin(), edge.end());
    int bind = 0;

    for(int i = 0; i < m; i++){
        if(bind < bridge.size() && bridge[bind] == edge[i]){
            bind++;
            continue;
        }
        auto[u, v] = edge[i];
        adj2[u].pb(v);
        adj2[v].pb(u);
    }
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
        par[i] = i;
        sz[i] = 1;
    }
    int cnt = 0, ans = 0;

    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            dfs2(i, cnt);
            sz[i] = cnt;
            ans += cnt * (cnt - 1) * (cnt - 2); // 3 here, 0 other
            ans += (cnt - 1) * (cnt - 1) * (clsz[cl[i]] - cnt) * 2; // 2 here, 1 other
            cnt = 0;
        }
    }

    for(int i = 0; i < bridge.size(); i++){
        auto[u, v] = bridge[i];
        u = find(u), v = find(v);
        adjb[u].pb(v);
        adjb[v].pb(u);
    }
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
    }
    for(int i = 1; i <= n; i++){
        if(vis[find(i)]) continue; 
        subcalc(find(i), find(i));
    }
    for(int i = 1; i <= n; i++){
        vis[i] = 0;
    }

    for(int i = 1; i <= n; i++){
        if(vis[find(i)]) continue;
        int k = find(i);
        int val = 0;
        dfs4(k, k, val);
        //cout<<i<<" -> "<<k<<" "<<val<<endl;
        dfs3(k, k, val, ans);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:131:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         if(bind < bridge.size() && bridge[bind] == edge[i]){
      |            ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:156:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int i = 0; i < bridge.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 26968 KB Output is correct
2 Correct 10 ms 27100 KB Output is correct
3 Correct 8 ms 26880 KB Output is correct
4 Correct 11 ms 27268 KB Output is correct
5 Correct 9 ms 26972 KB Output is correct
6 Correct 8 ms 26972 KB Output is correct
7 Incorrect 9 ms 26972 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 26968 KB Output is correct
2 Correct 10 ms 27100 KB Output is correct
3 Correct 8 ms 26880 KB Output is correct
4 Correct 11 ms 27268 KB Output is correct
5 Correct 9 ms 26972 KB Output is correct
6 Correct 8 ms 26972 KB Output is correct
7 Incorrect 9 ms 26972 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 72 ms 47188 KB Output is correct
2 Correct 85 ms 47956 KB Output is correct
3 Correct 96 ms 43920 KB Output is correct
4 Correct 93 ms 45916 KB Output is correct
5 Correct 78 ms 41068 KB Output is correct
6 Correct 89 ms 42180 KB Output is correct
7 Correct 80 ms 39880 KB Output is correct
8 Correct 91 ms 40852 KB Output is correct
9 Correct 79 ms 38344 KB Output is correct
10 Correct 92 ms 39112 KB Output is correct
11 Correct 68 ms 35844 KB Output is correct
12 Correct 67 ms 35660 KB Output is correct
13 Correct 73 ms 35524 KB Output is correct
14 Correct 59 ms 35268 KB Output is correct
15 Correct 49 ms 33992 KB Output is correct
16 Correct 49 ms 33736 KB Output is correct
17 Correct 11 ms 26968 KB Output is correct
18 Correct 11 ms 26972 KB Output is correct
19 Correct 11 ms 26972 KB Output is correct
20 Correct 12 ms 26972 KB Output is correct
21 Correct 11 ms 26972 KB Output is correct
22 Correct 11 ms 27100 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26972 KB Output is correct
2 Correct 9 ms 26972 KB Output is correct
3 Correct 9 ms 27120 KB Output is correct
4 Correct 9 ms 27224 KB Output is correct
5 Correct 9 ms 27228 KB Output is correct
6 Correct 9 ms 27280 KB Output is correct
7 Correct 9 ms 27128 KB Output is correct
8 Correct 9 ms 27228 KB Output is correct
9 Correct 9 ms 27264 KB Output is correct
10 Correct 9 ms 26972 KB Output is correct
11 Correct 10 ms 27228 KB Output is correct
12 Correct 9 ms 26972 KB Output is correct
13 Correct 9 ms 26972 KB Output is correct
14 Correct 9 ms 26972 KB Output is correct
15 Correct 9 ms 26972 KB Output is correct
16 Correct 9 ms 27108 KB Output is correct
17 Correct 10 ms 27224 KB Output is correct
18 Correct 9 ms 27224 KB Output is correct
19 Correct 9 ms 27228 KB Output is correct
20 Correct 9 ms 27224 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 37568 KB Output is correct
2 Correct 90 ms 38332 KB Output is correct
3 Correct 82 ms 38464 KB Output is correct
4 Correct 104 ms 38412 KB Output is correct
5 Correct 86 ms 38340 KB Output is correct
6 Correct 117 ms 46564 KB Output is correct
7 Correct 100 ms 44484 KB Output is correct
8 Correct 105 ms 42880 KB Output is correct
9 Correct 104 ms 41156 KB Output is correct
10 Correct 81 ms 38448 KB Output is correct
11 Correct 85 ms 38432 KB Output is correct
12 Correct 81 ms 38440 KB Output is correct
13 Correct 94 ms 38352 KB Output is correct
14 Correct 73 ms 37572 KB Output is correct
15 Correct 73 ms 36940 KB Output is correct
16 Correct 48 ms 34000 KB Output is correct
17 Correct 58 ms 40624 KB Output is correct
18 Correct 60 ms 39888 KB Output is correct
19 Correct 63 ms 40216 KB Output is correct
20 Correct 61 ms 39684 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 37612 KB Output is correct
2 Correct 83 ms 38228 KB Output is correct
3 Incorrect 93 ms 38600 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 26968 KB Output is correct
2 Correct 10 ms 27100 KB Output is correct
3 Correct 8 ms 26880 KB Output is correct
4 Correct 11 ms 27268 KB Output is correct
5 Correct 9 ms 26972 KB Output is correct
6 Correct 8 ms 26972 KB Output is correct
7 Incorrect 9 ms 26972 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 26968 KB Output is correct
2 Correct 10 ms 27100 KB Output is correct
3 Correct 8 ms 26880 KB Output is correct
4 Correct 11 ms 27268 KB Output is correct
5 Correct 9 ms 26972 KB Output is correct
6 Correct 8 ms 26972 KB Output is correct
7 Incorrect 9 ms 26972 KB Output isn't correct
8 Halted 0 ms 0 KB -