제출 #260622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260622		eohomegrownapps	Duathlon (APIO18_duathlon)	C++14	0 / 100	146 ms	16776 KiB

count_triplets

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

typedef long long ll;

vector<vector<int>> adjlist;
vector<vector<int>> bridgetree;
vector<int> comsize;
int nc;
int n;
int INF = 1e9;

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

    vector<int> components;
    int curcom = 0;

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

    void getHighest(int node, int parent){
        int highest = depth[node];
        hval[node]=highest;
        nodesvisited.push(node);
        for (int i : adjlist[node]){
            if (i==parent){continue;}
            if (depth[i]==INF){
                depth[i]=depth[node]+1;
                getHighest(i,node);
            }
            int 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);
        depth[0]=0;
        getHighest(0,-1);
        processComponent(0);
        if (nodesvisited.size()>0){
            comsize.push_back(nodesvisited.size());
            while (nodesvisited.size()>0){
                int t = nodesvisited.top();
                components[t]=curcom;
                nodesvisited.pop();
            }
            curcom++;
        }

        bridgetree.resize(curcom);
        nc = curcom;

        for (int i = 0; i<n; i++){
            for (int j : adjlist[i]){
                int ix = components[i];
                int jx = components[j];
                if (ix!=jx){
                    bridgetree[ix].push_back(jx);
                    bridgetree[jx].push_back(ix);
                }
            }
        }
        for (int 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<int> subtreesize;
vector<int> depth;
ll dfs(int node, int parent){
    ll tot = 0;
    subtreesize[node]=comsize[node];
    int ccnt = 0;
    for (int i : bridgetree[node]){
        if (i==parent){continue;}
        depth[i]=depth[node]+1;
        tot+=dfs(i,node);
        subtreesize[node]+=subtreesize[i];
        ccnt++;
    }
    ll childrentot = subtreesize[node]-comsize[node];
    if (ccnt>=2){
        for (int i : bridgetree[node]){
            tot+=comsize[node]*subtreesize[i]*(childrentot-subtreesize[i]);
        }
    }
    
    //consider starting at node and going up
    tot+=2*depth[node]*childrentot;
    return tot;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int m;
    cin>>n>>m;
    adjlist.resize(n);
    for (int i = 0; i<m; i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }
    
    tarjan::runBridgeDecom();

    /*for (int i = 0; i<n; i++){
        cout<<"("<<i<<": "<<tarjan::components[i]<<") ";
    }cout<<'\n';
    for (int i = 0; i<bridgetree.size(); i++){
        cout<<i<<" ("<<comsize[i]<<"): ";
        for (int j : bridgetree[i]){
            cout<<j<<", ";
        }cout<<'\n';
    }*/

    ll ans = 0;

    // within one component

    for (int i = 0; i<nc; i++){
        if (comsize[i]>=3){
            ans+=comsize[i]*(comsize[i]-1)*(comsize[i]-2);
        }
    }
    //cout<<ans<<'\n';

    //s+m in one component, e in other (or vice versa)
    for (int i = 0; i<nc; i++){
        if (comsize[i]>=2){
            ans+=2*((comsize[i]-1)*(comsize[i]-1))*(n-comsize[i]);
        }
    }
    //cout<<ans<<'\n';
    //all three in different components
    subtreesize.resize(nc);
    depth.resize(nc);
    cout<<ans+dfs(0,-1)<<'\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 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