Submission #698643

#	Time	Username	Problem	Language	Result	Execution time	Memory
698643		vjudge1	Duathlon (APIO18_duathlon)	C++17	66 / 100	110 ms	27960 KiB

count_triplets

#include<bits/stdc++.h>
#define maxn 200500
using namespace std;
int n,m;
vector<int> g[maxn];
bool vis[maxn];
int disc[maxn];
int low[maxn];
bool br[maxn];
int par[maxn];
int cnt[maxn];
bool c_vis[maxn];
int ct=0;
int tot;
vector<pair<int,int> > b[maxn];
int sz[maxn];
void dfs(int u,int p=-1) {
    tot++;
    vis[u]=true;
    disc[u]=low[u]=ct++;
    sz[u]=1;
    for(auto v:g[u]) {
        if(!vis[v]) {
            dfs(v,u);
            sz[u]+=sz[v];
            par[v]=u;
            low[u]=min(low[u],low[v]);
            if(low[v]>disc[u]) {
                br[v]=true;
            }
        }
        else {
            if(v!=p) low[u]=min(low[u],disc[v]);
        }
    }
}
void dfs_2(int u,int cur) {
    c_vis[u]=true;
    if(br[u]) cur=u;
    for(auto v:g[u]) {
        if(!c_vis[v]) {
            if(br[v]) {
                b[cur].push_back({u,v});
                b[v].push_back({v,cur});
            }
            dfs_2(v,cur);
        }
    }
}
void dfs_3(int u,int p=-1) {
    cnt[u]=sz[u];
    for(auto v:b[u]) {
        if(v.second!=p) {
            cnt[u]-=sz[v.second];
            dfs_3(v.second,u);
        }
    }
}
long long ans=0;
int mp[maxn];
void dfs_4(int u,int p=-1) {
    int pc=n-sz[u];
    vector<pair<int,int> > szs;
    for(auto v:b[u]) {
        if(v.second!=p) {
            mp[v.first]+=sz[v.second];
        }
        else {
            mp[v.first]+=(tot-sz[u]);
        }
    }
    for(auto v:b[u]) {
        if(v.second!=p) {
            szs.push_back({sz[v.second],mp[v.first]});
        }
        else {
            szs.push_back({tot-sz[u],mp[v.first]});
        }
    }
    for(auto v:b[u]) {
        mp[v.first]=0;
    }
    ans = ans+1ll*cnt[u]*(cnt[u]-1)*(cnt[u]-2);
    //cout<<u<<" "<<ans<<endl;
    for(auto c:szs) {
        //cout<<"\t"<<c.first<<" "<<c.second<<endl;
        int s=c.first;
        int a=tot-c.second-cnt[u];
        if(cnt[u]>=2) {
            ans=ans+2ll*(cnt[u]-1)*(cnt[u]-2)*s;
            ans=ans+2ll*(cnt[u]-1)*s;
        }
        //cout<<u<<" "<<ans<<endl;
        ans=ans+1ll*(cnt[u]-1)*s*a;
        ans=ans+1ll*s*(tot-s-cnt[u]);
    }
    //cout<<u<<" "<<ans<<endl;
    for(auto v:b[u]) {
        if(v.second!=p) dfs_4(v.second,u);
    }
}
/*int brute() {
    for(int c=1;c<=n;c++) {
        dfs_5(c);
    }
}*/
int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int u=1;u<=n;u++) {
        if(!vis[u]) {
            tot=0;
            dfs(u);
            dfs_2(u,u);
            dfs_3(u,u);
            dfs_4(u,u);
        }
    }
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs_4(int, int)':
count_triplets.cpp:62:9: warning: unused variable 'pc' [-Wunused-variable]
   62 |     int pc=n-sz[u];
      |         ^~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

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