제출 #772001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772001		gagik_2007	철인 이종 경기 (APIO18_duathlon)	C++17	10 / 100	1083 ms	25676 KiB

count_triplets

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=3e5+7;
const ll LG=25;
ll n,m,k;
vector<int>g[N];
bool used[N];
bool cikli_papa[N];
int cikl[N];
int a[N];
vector<int>cikler;
set<pair<int,int>>koxer;
vector<int>gg[N];
int up[N][LG];
int dist[N][LG];
int tin[N],tout[N];
int timer=0;
bool arinq[N];
int comp[N];

int ciklGti(int p, int v, int par){
    used[v]=true;
    for(int to:g[v]){
        if(!used[to]){
            int res=ciklGti(p, to, v);
            if(res!=-1){
                if(cikli_papa[v])cikl[p]=v;
                return res + 1;
            }
        }
        else if(to==p&&to!=par){
            if(cikli_papa[v])cikl[p]=v;
            return 1;
        }
    }
    return -1;
}

void dfs(int v, int par=-1){
    tin[v]=timer++;
    up[v][0]=(par==-1?v:par);
    dist[v][0]=(par==-1?0:a[par]);
    for(int to:gg[v]){
        if(to!=par){
            dfs(to,v);
        }
    }
    tout[v]=timer++;
}

bool is_papa(int v, int u){
    return (tin[v]<=tin[u]&&tout[v]>=tout[u]);
}

void lca_precalc() {
    for(int i=1;i<LG;i++){
        for(int v=1;v<=n;v++){
            up[v][i]=up[up[v][i-1]][i-1];
            dist[v][i]=dist[v][i-1]+dist[up[v][i-1]][i-1];
        }
    }
}

int lca(int v, int u){
    if(is_papa(v,u))return v;
    if(is_papa(u,v))return u;
    for(int i=LG-1;i>=0;i--){
        if(!is_papa(up[v][i],u)){
            v=up[v][i];
        }
    }
    return up[v][0];
}

int find_dist(int v, int u){
    if(v==u)return a[v];
    int papa=lca(u,v);
    int ans=0;
    for(int i=LG-1;i>=0;i--){
        if(!is_papa(up[v][i],papa)){
            ans+=dist[v][i];
            v=up[v][i];
        }
    }
    for(int i=LG-1;i>=0;i--){
        if(!is_papa(up[u][i],papa)){
            ans+=dist[u][i];
            u=up[u][i];
        }
    }
    ans+=a[v];
    ans+=a[u];
    if(papa!=v&&papa!=u){
        ans+=a[papa];
    }
    return ans;
}

void findComp(int c, int v){
    comp[v]=c;
    for(int to:g[v]){
        if(comp[to]==0){
            findComp(c,to);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    // auto start = std::chrono::high_resolution_clock::now();
    for(int v=1;v<=n;v++){
        fill(used,used+n+1,false);
        int res=ciklGti(v,v,v);
        if(res!=-1){
            if(cikl[v]==0){
                cikl[v]=v;
                cikli_papa[v]=true;
                cikler.push_back(v);
                a[v]=res;
            }
        }
        else{
            cikl[v]=v;
            cikler.push_back(v);
            a[v]=1;
        }
    }
    // cout<<endl;
    // for(int v:cikler)cout<<v<<" "<<a[v]<<endl;
    // cout<<endl;
    // for(int v=1;v<=n;v++){
    //     cout<<cikl[v]<<" ";
    // }
    // cout<<endl;
    for(int v=1;v<=n;v++){
        for(int to:g[v]){
            if(cikl[v]!=cikl[to])
            koxer.insert({cikl[v],cikl[to]});
            if(cikl[v]!=cikl[to])
            koxer.insert({cikl[to],cikl[v]});
        }
    }
    for(auto e:koxer){
        // cout<<e.ff<<" "<<e.ss<<endl;
        gg[e.ff].push_back(e.ss);
    }
    // auto end = std::chrono::high_resolution_clock::now();
    // auto dur = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
    // cout<<dur.count()<<" microseconds "<<endl;
    for(int v:cikler){
        if(tout[v]==0){
            dfs(v);
        }
    }
    lca_precalc();
    int cur=1;
    for(int v=1;v<=n;v++){
        if(comp[v]==0){
            findComp(cur++,v);
        }
    }
    ll ans=0;
    for(int v:cikler){
        for(int u:cikler){
            if(u!=v&&comp[u]==comp[v]){
                int cur=find_dist(u,v);
                ans+=cur-a[u]-a[v];
                ans+=(cur-a[u]-1)*(a[v]-1);
                ans+=(cur-a[v]-1)*(a[u]-1);
                ans+=(cur-2)*(a[v]-1)*(a[u]-1);
            }
        }
    }
    for(int v:cikler){
        ans+=a[v]*(a[v]-1)*(a[v]-2);
    }
    cout<<ans<<endl;
}

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