Submission #901635

#	Time	Username	Problem	Language	Result	Execution time	Memory
901635		SalihSahin	Duathlon (APIO18_duathlon)	C++17	31 / 100	117 ms	47956 KiB

count_triplets

#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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10