Submission #262238

#TimeUsernameProblemLanguageResultExecution timeMemory
262238Rouge_HugoDuathlon (APIO18_duathlon)C++14
66 / 100
208 ms33144 KiB
#include<bits/stdc++.h> #define fi first #define ll long long #define pb push_back #define se second using namespace std; int n,m; ll re=0; int szz=0; const int N=200009; vector<pair<int,int>>v[N]; vector<pair<int,int>>v1[N]; ll cnt=1,t[N],num[N],a[N],low[N],bridge[N],b[N],par[N],vis[N],sz[N],bo[N]; int tt=0; vector<int>nd; void dfs (int x,int p) { nd.pb(x); vis[x]=1; low[x]=num[x]=++tt; for(auto it:v[x]) { if (num[it.first]==0) dfs(it.first,x); if (num[x]<low[it.first]) bridge[it.second]=1; if (it.first!=p) low[x]=min(low[x],low[it.first]); } if(low[x] == num[x]) { int w=1; while(nd.back() != x) { par[nd.back()] = cnt; nd.pop_back();w++; } par[nd.back()] = cnt; nd.pop_back(); bo[cnt]=w; cnt++; } } void dfs2(int x,int p) { vis[x]=1; for(auto it:v[x]) { if(it.fi==p)continue; if (!vis[it.first]) dfs2(it.first,x); if (bridge[it.second]==1) { v1[par[x]].push_back({par[it.fi],x}); v1[par[it.fi]].push_back({par[x],it.fi}); } } } void solve(int x,int p) { vis[x]=1; for(auto it:v1[x]) { if(it.fi==p)continue; solve(it.fi,x); sz[x]+=sz[it.fi]; } sz[x]+=bo[x]; } void go (int x,int p,ll up) { vis[x]=1; sz[x]-=bo[x]; if(bo[x]>=3) re+=bo[x]*(bo[x]-1)*(bo[x]-2); re+=(up)*((bo[x])-1)*((bo[x])-1)*2; re+=(sz[x])*(bo[x]-1)*(bo[x]-1)*2;int u=0; for(auto it:v1[x]) { if(it.fi==p) { u=it.se; } if(it.fi==p)continue; re+=2*(t[x]-a[it.se])*sz[it.fi]*(bo[x]); re+=2*a[it.se]*sz[it.fi]; a[it.se]+=sz[it.fi]; t[x]+=sz[it.fi]; go(it.fi,x,up+bo[x]+sz[x]-sz[it.fi]); } re+=2*up*bo[x]*(sz[x]-a[u]); re+=2*up*a[u]; } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); scanf("%d %d", &n, &m); int x,y; for(int i=0; i<m; i++) { scanf("%d %d", &x, &y); v[x].push_back({y,i}); v[y].push_back({x,i}); } memset (vis,0,sizeof vis); for(int i=1;i<n+1;i++) { if(vis[i])continue; dfs(i,-1); } memset (vis,0,sizeof vis); for(int i=1;i<n+1;i++) { if(vis[i])continue; dfs2(i,-1); } memset (vis,0,sizeof vis); for(int i=1;i<cnt;i++) { if(vis[i])continue; solve(i,0); } re=0; memset (vis,0,sizeof vis); for(int i=1;i<cnt;i++) { if(vis[i])continue; go(i,0,0); } cout<<re; }

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...