Submission #487136

#	Time	Username	Problem	Language	Result	Execution time	Memory
487136		Redhood	Duathlon (APIO18_duathlon)	C++14	31 / 100	319 ms	29324 KiB

count_triplets

#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;
#define int long long
const int N = (int)1e5 + 10;
const int M = (int)2e5 + 10;
vector < pair < int , int > > edges;
vector < int > g[N], tree[N];
int fup[N], tin[N], T, used[N];
bool bridge[M];
int get(int ide, int v){
    return (edges[ide].fi == v ? edges[ide].se : edges[ide].fi);
}
void dfs(int v, int p){
    fup[v] = tin[v] = T++;
    used[v] = 1;
    for(auto &e : g[v]){
        int to = get(e , v);
        if(!used[to]){
            dfs(to, e);
        }
        if(e != p){
            fup[v] = min(fup[v] , fup[to]);
        }
    }
    if(p != -1){
        if(fup[v] == tin[v]){
            bridge[p] = 1;
        }
    }
}
int sz[N];

void colorit(int v, int clr){
    used[v] = clr;
    sz[clr]++;
    for(auto &e : g[v]){
        int to = get(e , v);
        if(bridge[e]){
            if(used[to] && used[to] != clr){
                tree[used[to]].pb(clr);
                tree[clr].pb(used[to]);
            }
            continue;
        }
        if(!used[to]){
            colorit(to , clr);
        }
    }
}
int h[N];

ll ans3, ans2, ans1;



int dead[N], s[N];
void sizes(int v, int p){
    s[v] = 1;
    for(auto &u : tree[v]){
        if(!dead[u] && u != p){
            sizes(u , v);
            s[v] += s[u];
        }
    }
}
int find_cen(int v , int p, int n){
    for(auto &u : tree[v]){
        if(u != p && !dead[u] && s[u] > n / 2)
            return find_cen(u, v , n);
    }
    return v;
}
void dfs1(int v, int p, int H, vector < int > &layer){
    h[v] = H;
    layer.pb(v);
    for(auto &u : tree[v]){
        if(u == p || dead[u])
            continue;
        dfs1(u , v , H + sz[v], layer);
    }
}
vector < int > now;
int cdused[N];
void decompose(int v){
    now.pb(v);
    dead[v] = 1;
    cdused[v] = 1;
    vector < vector < int > > sons;
    for(auto &u : tree[v]){
        if(!dead[u]){
            vector < int > curlayer;
            dfs1(u , -1, sz[v], curlayer);
            sons.pb(curlayer);
        }
    }
    ll sumSmH = 0, sumS = 0;


    for(int f = 0; f < sz(sons); ++f){
        for(auto &i : sons[f]){
            sumS += sz[i];
            sumSmH += 1ll * sz[i] * h[i];
        }
    }

    for(int f = 0; f < sz(sons); ++f){
        /// delete

        ll curS = 0, curSmH =0;
        for(auto &i : sons[f]){
            curS += sz[i];
            curSmH += 1ll * sz[i] * h[i];
        }


        for(auto &i : sons[f]){
            ans3 += 1ll * sz[i] * (h[i] - sz[v]) * (sumS - curS);
            ans3 += 1ll * sz[i] * (sumSmH - curSmH);

            ans3 += 1ll * sz[i] * sz[v] * (h[i] - sz[v]) * 2;
        }
    }

    for(auto &u : tree[v]){
        if(!dead[u]){
            sizes(u , -1);
            decompose(find_cen(u , -1 , s[u]));
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n , m;
    cin >> n >> m;


    for(int i = 0 ; i < m; ++i){
        int u , v;
        cin >> u >> v;
        --u , --v;
        edges.pb({u , v});
        g[u].pb(i);
        g[v].pb(i);
    }

    for(int i = 0; i < n; ++i){
        if(!used[i])
        dfs(i , -1);
    }

    /// find t


    int t = 0;
    fill(used , used + N , 0);
    for(int i = 0 ; i < n; ++i){
        if(!used[i]){
            t++;
            colorit(i , t);
        }
    }

//    /// COMPS
//    for(int i = 0 ; i < n; ++i)
//        cout << used[i] << ' ';
//    cout << endl;
//    cout << " EDGES TREE\n";
//    for(int i = 1;i <= t; ++i){
//        for(auto &u : tree[i])
//            cout << i << ' ' << u << endl;
////        cout << endl;
//    }
//
//    cout << endl;


    for(int j = 1; j <= t; ++j){
        if(cdused[j])
            continue;
        now.clear();
        sizes(j , -1);
        decompose(find_cen(j , -1 , s[j]));

        /// calc ans2 and ans1




        ll ONE = 0, SEC = 0;
        for(int i : now){
            ONE += sz[i];
            SEC += (sz[i] * (sz[i] - 1));
        }

        for(int i : now){
            ans2 += 1ll * ((sz[i]-1)*(sz[i]-2) + (sz[i]-1)) * (ONE - sz[i]) * 2;
            ans1 += 1ll * (1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2));
        }

    }
//    cout << ans1 << ' ' << ans2 << ' ' << ans3 << endl;
    cout << ans1 + ans2 + ans3 << endl;
    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7


1 1 1
100000000 1 1 1
1


11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1


4 3
1 2
2 3
3 4


4 4
1 2
2 3
3 4
4 2


6 4
1 2
2 3
4 5
5 6
*/

• 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