Submission #372734

#TimeUsernameProblemLanguageResultExecution timeMemory
372734BartolMDuathlon (APIO18_duathlon)C++17
31 / 100
154 ms19176 KiB
#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back typedef long long ll; typedef pair <int, int> pii; typedef pair <int, pii> pip; typedef pair <pii, int> ppi; typedef pair <ll, ll> pll; const int INF=0x3f3f3f3f; const int N=1e5+5; int n, m, dtime=1; ll sol=0; int cnt[N], siz[N], P[N]; int dt[N], lw[N]; vector <int> ls[N], ls2[N]; vector <pii> ed; #define DEBUG 0 int name(int x) { if (x==P[x]) return x; P[x]=name(P[x]); return P[x]; } void mrg(int a, int b) { a=name(a); b=name(b); if (a==b) return; P[a]=b; siz[b]+=siz[a]; } void rek(int node, int par) { dt[node]=dtime++; lw[node]=dt[node]; for (int sus:ls[node]) { if (sus==par) continue; if (dt[sus]==0) { rek(sus, node); lw[node]=min(lw[node], lw[sus]); } else { //backedge lw[node]=min(lw[node], dt[sus]); } } if (par && lw[node]==dt[node]) { //bridge ed.pb(mp(node, par)); #if DEBUG printf("bridge %d -> %d\n", node, par); #endif } else if (par) { mrg(node, par); #if DEBUG printf("mrgam %d i %d\n", node, par); #endif } } void dfs(int node, int par) { cnt[node]=siz[node]; for (int sus:ls2[node]) { if (sus==par) continue; dfs(sus, node); cnt[node]+=cnt[sus]; } } void calc(int node, int par, int uk) { sol+=(ll)siz[node]*(siz[node]-1)*(siz[node]-2); int iz=uk-siz[node]; for (int sus:ls2[node]) { if (sus==par) continue; calc(sus, node, uk); iz-=cnt[sus]; sol+=(ll)cnt[sus]*(uk-cnt[sus]-siz[node])*siz[node]; if (siz[node]>2) sol+=(ll)cnt[sus]*(siz[node]-1)*(siz[node]-1)*2; } sol+=(ll)iz*(uk-iz-siz[node])*siz[node]; if (siz[node]>2) sol+=(ll)iz*(siz[node]-1)*(siz[node]-1)*2; } void solve() { for (int i=1; i<=n; ++i) P[i]=i, siz[i]=1; for (int i=1; i<=n; ++i) { if (dt[i]) continue; dtime=1; ed.clear(); rek(i, 0); for (pii pp:ed) { ls2[name(pp.X)].pb(name(pp.Y)); ls2[name(pp.Y)].pb(name(pp.X)); } } for (int i=1; i<=n; ++i) { sort(ls2[i].begin(), ls2[i].end()); ls2[i].erase(unique(ls2[i].begin(), ls2[i].end()), ls2[i].end()); #if DEBUG printf("node: %d, siz: %d, sus: ", i, siz[i]); for (int sus:ls2[i]) printf("%d ", sus); printf("\n"); #endif // DEBUG } for (int i=1; i<=n; ++i) { if (cnt[i] || P[i]!=i) continue; dfs(i, 0); calc(i, 0, cnt[i]); } printf("%lld\n", sol); } void load() { scanf("%d %d", &n, &m); for (int i=0; i<m; ++i) { int a, b; scanf("%d %d", &a, &b); ls[a].pb(b); ls[b].pb(a); } } int main() { load(); solve(); return 0; } /* 8 7 2 4 4 7 6 8 3 8 5 6 5 8 6 7 */

Compilation message (stderr)

count_triplets.cpp: In function 'void load()':
count_triplets.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#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...