Submission #1161724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161724		Otalp	Duathlon (APIO18_duathlon)	C++20	23 / 100	158 ms	52696 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
#define int ll

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

vector<int> q[200100], dq[200100], ddq[200100];
int pos[200100], timer=0;
int fp[200100];
vector<pii> brs;
map<pii, int> br;
int ar[201000];
int dc[200100], dsz[200100];
vector<int> ars;

void ddfs0(int v, int p, int cl){
    fp[v] = pos[v] = ++timer;
    int chld = 0;
    dc[v] = cl;
    dsz[cl] ++;
    for(int to: ddq[v]){
        if(to == p) continue;
        if(pos[to]){
            fp[v] = min(pos[to], fp[v]);
            continue;
        }
        ddfs0(to, v, cl);
        fp[v] = min(fp[to], fp[v]);
        if(ar[v] == 0 and fp[v] <= pos[to] and p != 0){
            ar[v] = 1;
            ars.pb(v);
        }
        chld ++;
    }
    if(p == 0 and chld > 1){
        ar[v] = 1;
        ars.pb(v);
    }
}


int ddcl[200100];

void ddfs1(int v, int cl){
    ddcl[v] = cl;
    pos[v] = 1;
    if(ar[v]) return;
    for(int to: ddq[v]){
        if(pos[to] or ar[to]) continue;
        ddfs1(to, cl);
    }
}

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;
        ddq[l].pb(r);
        ddq[r].pb(l);
    }
    for(int i=1; i<=n; i++){
        pos[i] = 0;
    }
    int dls = 0;
    for(int i=1; i<=n; i++){
        if(!pos[i]) ddfs0(i, 0, ++dls);
    }
    for(int i=1; i<=n; i++) pos[i] = 0;
    dls = 0;
    for(int i=1; i<=n; i++){
        if(!pos[i]) ddfs1(i, ++dls);
    }
    // for(int x: ars) cout<<x<<'\n';

    for(int v: ars){
        for(int to: ddq[v]){
            dq[ddcl[v]].pb(ddcl[to]);
            if(!ar[to]){
                dq[ddcl[to]].pb(ddcl[v]);
            }
        }
    }
    
    n = dls;

    // for(int i=1; i<=n; i++){
    //     for(int to: dq[i]){
    //         cout<<i<<' '<<to<<'\n';
    //     }
    // }

    //bc-tree stage 2
    timer = 0;
    for(int i=1; i<=n; i++) pos[i] = 0;
    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;
}

signed 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: 0 / 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