Submission #136251

#TimeUsernameProblemLanguageResultExecution timeMemory
136251baluteshihDuathlon (APIO18_duathlon)C++14
100 / 100
191 ms27656 KiB
#include <bits/stdc++.h> #define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define pb push_back #define ET cout << "\n" #define F first #define S second #define MP make_pair #define MEM(i,j) memset(i,j,sizeof i) #define ALL(v) v.begin(),v.end() #define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}; using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; vector<ll> G[100005],BG[100005]; ll low[100005],dfn[100005],comp[100005],req[100005],avsub[100005],sub[100005],dft; ll ans1,ans2,c; stack<ll> st; bitset<100005> vis; void con(int u) { vis[u]=1,++c; for(ll i:G[u]) if(!vis[i]) con(i); } void dfs(int u,int f) { ll usq=0; low[u]=dfn[u]=++dft,sub[u]=1,comp[u]=c,avsub[u]=1; st.push(u); for(ll i:G[u]) if(i!=f) if(!dfn[i]) { dfs(i,u),sub[u]+=sub[i]; if(low[i]>=dfn[u]) { ll sq=0; vector<ll> v; avsub[u]+=sub[i]; for(int x=-1;x!=i;) { x=st.top(),st.pop(); sq+=avsub[x]*avsub[x]; v.pb(x); } for(ll j:v) req[j]+=(c-sub[i])*(c-sub[i])+sq-avsub[j]*avsub[j]; req[u]+=sq; } else low[u]=min(low[u],low[i]); } else if(dfn[u]>dfn[i]) low[u]=min(low[u],dfn[i]); } int main() {jizz ll m,a,b,n,ans=0; cin >> n >> m; while(m--) cin >> a >> b,G[a].pb(b),G[b].pb(a); for(int i=1;i<=n;++i) if(!vis[i]) c=0,con(i),dfs(i,i); for(int i=1;i<=n;++i) ans+=(comp[i]-1)*(comp[i]-1)-req[i]; cout << ans << "\n"; }

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:36:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if(i!=f)
     ^
count_triplets.cpp:32:5: warning: unused variable 'usq' [-Wunused-variable]
  ll usq=0;
     ^~~
#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...