Submission #49245

#TimeUsernameProblemLanguageResultExecution timeMemory
49245BTheroDuathlon (APIO18_duathlon)C++17
25 / 100
1064 ms19540 KiB
// Why am I so stupid? :c #include <bits/stdc++.h> #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define fi first #define se second typedef long long ll; using namespace std; struct edge { int u, v; edge() { u = v = 0; } } e[200005]; int tin[100005], fup[100005]; vector <int> adj[100005]; vector <int> cp[100005]; bool bad[200005]; int col[100005]; bool u[200005]; int timer, sz; int n, m; ll ans; void dfs(int v, int pr) { tin[v] = fup[v] = ++timer; u[v] = 1; for (int id : adj[v]) { int to; if (v == e[id].u) { to = e[id].v; } else { to = e[id].u; } if (to == pr) { continue; } if (u[to]) { fup[v] = min(fup[v], tin[to]); } else { dfs(to, v); fup[v] = min(fup[v], fup[to]); if (fup[to] > tin[v]) { bad[id] = 1; } } } } void dfs2(int v) { cp[sz].pb(v); u[v] = 1; for (int to : adj[v]) { if (u[to]) { continue; } dfs2(to); } } void calc(int v, int st, int mlt, int cur) { if (st != v) { int a = cp[st].size(); int b = cp[v].size(); ans += 1ll * (a - 1) * (b - 1) * (mlt + a - 1 + b - 1); ans += 1ll * (b - 1) * (mlt + b - 1); ans += 1ll * (a - 1) * (mlt + a - 1); ans += 1ll * mlt; } u[v] = 1; for (int id : adj[v]) { bool good = 1; int to, nxt; if (col[e[id].v] == v) { if (e[id].v == cur || cur == -1) { good = 0; } nxt = e[id].u; } else { if (e[id].u == cur || cur == -1) { good = 0; } nxt = e[id].v; } to = col[nxt]; if (u[to]) { continue; } calc(to, st, mlt + 1 + good * (cp[v].size() - 1), nxt); } } ll f(ll x) { return x * (x - 1) * (x - 2); } void solve() { scanf("%d %d", &n, &m); for (int i = 1; i <= m; ++i) { scanf("%d %d", &e[i].u, &e[i].v); adj[e[i].u].pb(i); adj[e[i].v].pb(i); } for (int i = 1; i <= n; ++i) { if (u[i]) { continue; } dfs(i, -1); } for (int i = 1; i <= n; ++i) { adj[i].clear(); u[i] = 0; } for (int i = 1; i <= m; ++i) { if (!bad[i]) { adj[e[i].u].pb(e[i].v); adj[e[i].v].pb(e[i].u); } } for (int i = 1; i <= n; ++i) { if (u[i]) { continue; } ++sz; dfs2(i); for (int it : cp[sz]) { col[it] = sz; } } for (int i = 1; i <= n; ++i) { adj[i].clear(); u[i] = 0; } for (int i = 1; i <= m; ++i) { if (bad[i]) { adj[col[e[i].v]].pb(i); adj[col[e[i].u]].pb(i); } } for (int i = 1; i <= sz; ++i) { ans += f(cp[i].size()); for (int j = 1; j <= sz; ++j) { u[j] = 0; } calc(i, i, -1, -1); } printf("%lld\n", ans); } int main() { #ifdef BThero freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // BThero int tt = 1; while (tt--) { solve(); } return 0; }

Compilation message (stderr)

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