Submission #1162395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162395		Otalp	Duathlon (APIO18_duathlon)	C++20	31 / 100	253 ms	68360 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 pos[v] <= fp[to] and p != 0){
            ar[v] = 1;
            ars.pb(v);
            // cout<<v<<'\n';
        }
        chld ++;
    }
    if(p == 0 and chld > 1){
        ar[v] = 1;
        ars.pb(v);
    }
}


int ddcl[200100], da[200100], dda[200100], db[200100], b[200200];
map<int, int> us;

void ddfs1(int v, int cl){
    ddcl[v] = cl;
    pos[v] = 1;
    da[cl] ++;
    dsz[cl] ++;
    db[cl] = 0;
    if(ar[v]){
        db[cl] = 1;
        return;
    }
    for(int to: ddq[v]){
        if(ar[to] and !us[to]) us[to] = 1, dsz[cl] ++;
        if(pos[to] or ar[to]) continue;
        ddfs1(to, cl);
    }
}

void dfs0(int v, int p){
    fp[v] = pos[v] = ++timer;
    int pcnt = 0;
    for(int to: dq[v]){
        if(to == p and pcnt == 0){
            // pcnt ++;
            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] += da[v];
    dda[cl] += dsz[v];
    b[cl] |= db[v];
    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(!b[v]) k += a[v] - 1;
    if(a[v] == 1) k = 0;
    // cout<<v<<' '<<k<<'\n';
    ans += h * k * 2;
    for(int to: q[v]){
        if(to == p) continue;
        ans += sz[to] * k * 2;
        sum += sz[to];
    }
    if(b[v]){
        for(int to: q[v]){
            if(b[to]) continue;
            ans += a[to] * (a[to] - 1);
        }
    }
    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]) us.clear(), ddfs1(i, ++dls);
    }
    // for(int x: ars) cout<<x<<'\n';
    set<pii> dd;
    for(int v: ars){
        for(int to: ddq[v]){
            if(dd.find({ddcl[v], ddcl[to]}) == dd.end()) dq[ddcl[v]].pb(ddcl[to]), dd.insert({ddcl[v], ddcl[to]});
            if(!ar[to]){
                if(dd.find({ddcl[to], ddcl[v]}) == dd.end()) dq[ddcl[to]].pb(ddcl[v]), dd.insert({ddcl[to], ddcl[v]});
            }
        }
    }
    //if(dd.find({ddcl[v], ddcl[to]}) == dd.end()) 
    
    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);
        // cout<<l<<' '<<r<<'\n';
    }
    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: 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