제출 #260654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260654		eohomegrownapps	철인 이종 경기 (APIO18_duathlon)	C++14	8 / 100	169 ms	21672 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<vector<ll>> adjlist;
vector<vector<ll>> bridgetree;
vector<ll> comsize;
vector<ll> majorcomponents;
vector<ll> minortomajor;
vector<ll> majsize;
ll majind = 0;
ll nc;
ll n;
ll INF = 1e9;

namespace tarjan{
    vector<ll> depth;
    vector<ll> hval;
    stack<ll> nodesvisited;

    vector<ll> components;
    ll curcom = 0;

    void processComponent(ll node){
        ll cnt = 1;
        while (nodesvisited.top()!=node){
            ll t = nodesvisited.top();
            components[t]=curcom;
            minortomajor[curcom]=majind;
            nodesvisited.pop();
            cnt++;
        }
        components[node]=curcom;
        nodesvisited.pop();
        comsize.push_back(cnt);
        curcom++;
    }

    void getHighest(ll node, ll parent){
        majorcomponents[node]=majind;
        ll highest = depth[node];
        hval[node]=highest;
        nodesvisited.push(node);
        for (ll i : adjlist[node]){
            if (i==parent){continue;}
            if (depth[i]==INF){
                depth[i]=depth[node]+1;
                getHighest(i,node);
            }
            ll hcur = hval[i];
            if (hcur<=depth[node]){
                //not a bridge
                highest=min(highest,hcur);
            } else {
                //bridge
                processComponent(i);
            }
        }
        hval[node]=highest;
    }

    void runBridgeDecom(){
        depth.resize(n,INF);
        hval.resize(n,n+1);
        components.resize(n);
        majorcomponents.resize(n);
        minortomajor.resize(n);
        for (int i = 0; i<n; i++){
            if (depth[i]!=INF){continue;}
            depth[i]=0;
            getHighest(i,-1);
            processComponent(i);
            if (nodesvisited.size()>0){
                comsize.push_back(nodesvisited.size());
                while (nodesvisited.size()>0){
                    ll t = nodesvisited.top();
                    components[t]=curcom;
                    nodesvisited.pop();
                }
                curcom++;
            }
            majind++;
        }
        majsize.resize(majind);
        for (int i = 0; i<n; i++){
            majsize[majorcomponents[i]]++;
        }

        bridgetree.resize(curcom);
        nc = curcom;

        for (ll i = 0; i<n; i++){
            for (ll j : adjlist[i]){
                ll ix = components[i];
                ll jx = components[j];
                if (ix!=jx){
                    bridgetree[ix].push_back(jx);
                    bridgetree[jx].push_back(ix);
                }
            }
        }
        for (ll i = 0; i<nc; i++){
            sort(bridgetree[i].begin(),bridgetree[i].end());
            bridgetree[i].erase(unique(bridgetree[i].begin(),bridgetree[i].end()),bridgetree[i].end());
        }
    }
}

vector<ll> subtreesize;
vector<ll> tdepth;
ll dfs(ll node, ll parent){
    //cout<<node<<' '<<parent<<'\n';
    ll tot = 0;
    subtreesize[node]=comsize[node];
    ll ccnt = 0;
    for (ll i : bridgetree[node]){
        if (i==parent){continue;}
        tdepth[i]=tdepth[node]+1;
        tot+=dfs(i,node);
        subtreesize[node]+=subtreesize[i];
        ccnt++;
    }
    ll childrentot = subtreesize[node]-comsize[node];
    if (ccnt>=2){
        for (ll i : bridgetree[node]){
            if (i==parent){continue;}
            tot+=comsize[node]*subtreesize[i]*(childrentot-subtreesize[i]);
        }
    }
    //cout<<"semit "<<tot<<'\n';
    //cout<<node<<" "<<tdepth[node]<<'\n';
    
    //consider starting at node and going up
    tot+=2*tdepth[node]*childrentot;
    //cout<<node<<": total "<<tot<<'\n';
    return tot;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll m;
    cin>>n>>m;
    adjlist.resize(n);
    for (ll i = 0; i<m; i++){
        ll a,b;
        cin>>a>>b;
        a--;b--;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }
    
    tarjan::runBridgeDecom();
    /*for (ll i = 0; i<n; i++){
        cout<<"("<<i<<": "<<tarjan::components[i]<<") ";
    }cout<<'\n';
    for (ll i = 0; i<bridgetree.size(); i++){
        cout<<i<<" ("<<comsize[i]<<"): ";
        for (ll j : bridgetree[i]){
            cout<<j<<", ";
        }cout<<'\n';
    }*/

    ll ans = 0;

    // within one component

    for (ll i = 0; i<nc; i++){
        if (comsize[i]>=3){
            ans+=comsize[i]*(comsize[i]-1)*(comsize[i]-2);
        }
    }
    /*cout<<ans<<'\n';
    for (int i : comsize){
        cout<<i<<'\n';
    }*/
    //s+m in one component, e in other (or vice versa)
    for (ll i = 0; i<nc; i++){
        if (comsize[i]>=2){
            //assert(majsize[majorcomponents[i]]-comsize[i]>0);
            ans+=2*((comsize[i]-1)*(comsize[i]-1))*(majsize[minortomajor[i]]-comsize[i]);
        }
    }
    //cout<<ans<<'\n';
    //all three in different components
    subtreesize.resize(nc);
    tdepth.resize(nc,INF);
    for (int i = 0; i<nc; i++){
        if (tdepth[i]!=INF){continue;}
        tdepth[i]=0;
        ans+=dfs(i,-1);
    }
    cout<<ans<<'\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10