Submission #1160963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160963		Otalp	Duathlon (APIO18_duathlon)	C++20	31 / 100	222 ms	39320 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int MAXA = 2e5 + 5;

vector<int> q[200100], dq[200100];
int pos[200100], timer=0;
int fp[200100];
vector<pii> brs;
map<pii, int> br;


void dfs0(int v, int p){
    fp[v] = pos[v] = ++timer;
    for(int to: dq[v]){
        if(to == p) continue;
        if(pos[to]){
            fp[v] = min(pos[to], fp[v]);
            continue;
        }
        dfs0(to, v);
        fp[v] = min(fp[to], fp[v]);
        if(fp[v] < fp[to]){
            br[{to, v}] = 1;
            br[{v, to}] = 1;
            brs.pb({v, to});
        }
    }
}

ll a[200100], c[200100];

void dfs1(int v, int cl){
    pos[v] = 1;
    c[v] = cl;
    a[cl] ++;
    for(int to: dq[v]){
        if(pos[to] or br[{v, to}]) continue;
        dfs1(to, cl);
    }
}

ll ans = 0;

ll sz[200100];

void dfs2(int v, int p){
    sz[v] = a[v];
    pos[v] = 1;
    for(int to: q[v]){
        if(to == p) continue;
        dfs2(to, v);
        sz[v] += sz[to];
    }
}

void dfs3(int v, int p, ll h){
    // cout<<a[v]<<' '<<c[v]<<'\n';
    ans += a[v] * (a[v] - 1) * (a[v] - 2);
    pos[v] = 1;
    ll sum = h;
    ll k = (a[v] * (a[v] - 1) - a[v] + 1);
    if(a[v] == 1) k = 0;
    ans += h * k * 2;
    for(int to: q[v]){
        if(to == p) continue;
        ans += sz[to] * k * 2;
        sum += sz[to];
    }
    ans += h * a[v] * (sum - h);
    for(int to: q[v]){
        if(to == p) continue;
        ans += sz[to] * a[v] * (sum - sz[to]);
        dfs3(to, v, sum + a[v] - sz[to]);
    }
}


void solve(){
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int l, r;
        cin>>l>>r;
        dq[l].pb(r);
        dq[r].pb(l);
    }

    for(int i=1; i<=n; i++){
        if(!pos[i]) dfs0(i, 0);
    }
    for(int i=1; i<=n; i++) pos[i] = 0;

    // return;
    int ls = 0;
    for(int i=1; i<=n; i++){
        if(!pos[i]){
            dfs1(i, ++ls);
        }
    }
    for(int i=1; i<=n; i++) pos[i] = 0;
    for(auto g: brs){
        int l = g.ff, r = g.ss;
        l = c[l];
        r = c[r];
        q[l].pb(r);
        q[r].pb(l);
    }
    for(int i=1; i<=ls; i++){
        if(!pos[i]){
            dfs2(i, 0);
        }
    }
    for(int i=1; i<=ls; i++) pos[i] = 0;
    ans = 0;
    for(int i=1; i<=ls; i++){
        if(!pos[i]){
            dfs3(i, 0, 0);
        }
    }
    cout<<ans;
}

int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<'\n';
    }
}

• 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