oj.uz

Submission #901628

# Submission time Handle Problem Language Result Execution time Memory
901628 2024-01-09T18:34:47 Z SalihSahin Duathlon (APIO18_duathlon) C++17
31 / 100
 117 ms 47332 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);
        }
    }
}

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;
        dfs3(find(i), find(i), sub[find(i)], ans);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:123: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]
  123 |         if(bind < bridge.size() && bridge[bind] == edge[i]){
      |            ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:148: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]
  148 |     for(int i = 0; i < bridge.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 26968 KB Output is correct
2 Correct 8 ms 27092 KB Output is correct
3 Correct 9 ms 27096 KB Output is correct
4 Correct 8 ms 26884 KB Output is correct
5 Correct 8 ms 26972 KB Output is correct
6 Correct 8 ms 26920 KB Output is correct
7 Incorrect 8 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 8 ms 26968 KB Output is correct
2 Correct 8 ms 27092 KB Output is correct
3 Correct 9 ms 27096 KB Output is correct
4 Correct 8 ms 26884 KB Output is correct
5 Correct 8 ms 26972 KB Output is correct
6 Correct 8 ms 26920 KB Output is correct
7 Incorrect 8 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 86 ms 47184 KB Output is correct
2 Correct 71 ms 47332 KB Output is correct
3 Correct 83 ms 43036 KB Output is correct
4 Correct 86 ms 46280 KB Output is correct
5 Correct 80 ms 41668 KB Output is correct
6 Correct 98 ms 42608 KB Output is correct
7 Correct 77 ms 40392 KB Output is correct
8 Correct 88 ms 41240 KB Output is correct
9 Correct 76 ms 38600 KB Output is correct
10 Correct 77 ms 39764 KB Output is correct
11 Correct 64 ms 36124 KB Output is correct
12 Correct 64 ms 35992 KB Output is correct
13 Correct 62 ms 35764 KB Output is correct
14 Correct 64 ms 35532 KB Output is correct
15 Correct 48 ms 34240 KB Output is correct
16 Correct 59 ms 34084 KB Output is correct
17 Correct 11 ms 26972 KB Output is correct
18 Correct 11 ms 27092 KB Output is correct
19 Correct 10 ms 26968 KB Output is correct
20 Correct 11 ms 26972 KB Output is correct
21 Correct 11 ms 26972 KB Output is correct
22 Correct 11 ms 26972 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 27180 KB Output is correct
4 Correct 8 ms 27120 KB Output is correct
5 Correct 8 ms 27228 KB Output is correct
6 Correct 8 ms 27228 KB Output is correct
7 Correct 8 ms 27228 KB Output is correct
8 Correct 8 ms 27228 KB Output is correct
9 Correct 8 ms 27228 KB Output is correct
10 Correct 8 ms 26972 KB Output is correct
11 Correct 10 ms 26972 KB Output is correct
12 Correct 8 ms 26972 KB Output is correct
13 Correct 8 ms 26972 KB Output is correct
14 Correct 10 ms 26972 KB Output is correct
15 Correct 9 ms 26972 KB Output is correct
16 Correct 9 ms 26972 KB Output is correct
17 Correct 8 ms 27228 KB Output is correct
18 Correct 9 ms 27240 KB Output is correct
19 Correct 8 ms 27228 KB Output is correct
20 Correct 10 ms 27228 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 37704 KB Output is correct
2 Correct 78 ms 37572 KB Output is correct
3 Correct 80 ms 37692 KB Output is correct
4 Correct 84 ms 37708 KB Output is correct
5 Correct 82 ms 37572 KB Output is correct
6 Correct 93 ms 45760 KB Output is correct
7 Correct 97 ms 43712 KB Output is correct
8 Correct 99 ms 42100 KB Output is correct
9 Correct 113 ms 40644 KB Output is correct
10 Correct 79 ms 37628 KB Output is correct
11 Correct 78 ms 38916 KB Output is correct
12 Correct 80 ms 38740 KB Output is correct
13 Correct 98 ms 38852 KB Output is correct
14 Correct 79 ms 38068 KB Output is correct
15 Correct 67 ms 36984 KB Output is correct
16 Correct 47 ms 34108 KB Output is correct
17 Correct 59 ms 41036 KB Output is correct
18 Correct 60 ms 40376 KB Output is correct
19 Correct 62 ms 40500 KB Output is correct
20 Correct 59 ms 40120 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26972 KB Output is correct
2 Correct 8 ms 26972 KB Output is correct
3 Incorrect 9 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 79 ms 37488 KB Output is correct
2 Correct 117 ms 37300 KB Output is correct
3 Incorrect 86 ms 37744 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 26968 KB Output is correct
2 Correct 8 ms 27092 KB Output is correct
3 Correct 9 ms 27096 KB Output is correct
4 Correct 8 ms 26884 KB Output is correct
5 Correct 8 ms 26972 KB Output is correct
6 Correct 8 ms 26920 KB Output is correct
7 Incorrect 8 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 8 ms 26968 KB Output is correct
2 Correct 8 ms 27092 KB Output is correct
3 Correct 9 ms 27096 KB Output is correct
4 Correct 8 ms 26884 KB Output is correct
5 Correct 8 ms 26972 KB Output is correct
6 Correct 8 ms 26920 KB Output is correct
7 Incorrect 8 ms 26972 KB Output isn't correct
8 Halted 0 ms 0 KB -