Submission #395155

#TimeUsernameProblemLanguageResultExecution timeMemory
395155CSQ31Duathlon (APIO18_duathlon)C++14
0 / 100
203 ms31240 KiB
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define sz(a) (int)(a.size()) #define all(a) a.begin(),a.end() #define lb lower_bound #define ub upper_bound #define owo ios_base::sync_with_stdio(0);cin.tie(0); #define MOD (ll)(998244353) #define INF (ll)(1e18) #define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr) #define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\ debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC)) typedef long long int ll; typedef long double ld; typedef pair<ll,ll> PII; typedef pair<int,int> pii; typedef vector<vector<int>> vii; typedef vector<vector<ll>> VII; ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);} const int MAXN = 2e5+5; int n,n2,timer = 0; vector<int>low(MAXN),tin(MAXN),sub(MAXN); vii g(MAXN),g2(MAXN); stack<int>stk; ll ans = 0,cnt = 0; void bbc(int v,int u){ cnt++; tin[v] = low[v] = ++timer; stk.push(v); for(int x:g[v]){ if(x!= u){ if(!tin[x]){ bbc(x,v); low[v] = min(low[v],low[x]); if(low[x] >= tin[v]){ n2++; g2[v].pb(n2); g2[n2].pb(v); while(g2[n2].back() != x){ g2[n2].pb(stk.top()); g2[stk.top()].pb(n2); stk.pop(); } } }else{ low[v] = min(low[v],tin[x]); } } } } void dfs(int v,int u){ sub[v] = (v<=n); for(int x:g2[v]){ if(x != u){ dfs(x,v); sub[v]+=sub[x]; } } } void dfs2(int v,int u){ for(int x:g2[v]){ if(x != u){ dfs2(x,v);//c is in this bbc if(v > n)ans-=(sz(g2[v]) - 1) * 1LL * sub[x] * 1LL *(sub[x]-1); //s and f is under this art vertex } } if(v > n)ans-=(sz(g2[v])-1) * 1LL * (n-sub[v]) * 1LL * (n-sub[v]-1); //try parent as art vertex } int main() { int m; cin>>n>>m; n2 = n; for(int i=0;i<m;i++){ int v,u; cin>>v>>u; g[v].pb(u); g[u].pb(v); } for(int i=1;i<=n;i++){ if(!tin[i]){ cnt = 0; bbc(i,-1); dfs(i,-1); //for(int i=1;i<=n2;i++)cout<<sub[i]<<" "; dfs2(i,-1); ans+=cnt*(cnt-1)*(cnt-2); } } cout<<ans<<'\n'; }
#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...