Submission #628281

#TimeUsernameProblemLanguageResultExecution timeMemory
628281Do_you_copyDuathlon (APIO18_duathlon)C++17
100 / 100
125 ms35396 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define pb push_back #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ull = unsigned ll; using ld = long double; using pii = pair <int, int>; using pil = pair <int, ll>; using pli = pair <ll, int>; using pll = pair <ll, ll>; mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); ll min(const ll &a, const ll &b){ return (a < b) ? a : b; } ll max(const ll &a, const ll &b){ return (a > b) ? a : b; } //const ll Mod = 1000000007; //const ll Mod2 = 999999999989; //only use when required const int maxN = 3e5 + 1; int n, m; vector <int> adj[maxN]; int low[maxN], num[maxN], timedfs; vector <int> S; vector <int> adj1[maxN]; int bcc; ll sz[maxN]; ll cnt, ans; void pre_dfs(int u, int p){ low[u] = num[u] = ++timedfs; S.pb(u); ++cnt; int child = 0; for (const int &i: adj[u]){ if (i == p) continue; if (!num[i]){ pre_dfs(i, u); ++child; low[u] = min(low[u], low[i]); if (low[i] >= num[u]){ ++bcc; adj1[u].pb(n + bcc); int v; do{ v = S.back(); S.pop_back(); adj1[bcc + n].pb(v); } while (v != i); } } else low[u] = min(low[u], num[i]); } } void dfs(int u, int p){ sz[u] = (u <= n); for (auto i: adj1[u]){ dfs(i, u); sz[u] += sz[i]; if (u > n) ans -= adj1[u].size() * sz[i] * (sz[i] - 1); } if (u > n) ans -= adj1[u].size() * (cnt - sz[u]) * (cnt - sz[u] - 1); } void Init(){ cin >> n >> m; for (int i = 1; i <= m; ++i){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } for (int i = 1; i <= n; ++i){ if (!num[i]){ cnt = 0; pre_dfs(i, i); ans += cnt * (cnt - 1) * (cnt - 2); dfs(i, i); } } cout << ans; } #define debu #define taskname "test" signed main(){ if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); #ifdef debug freopen(taskname".out", "w", stdout); #endif } faster; ll tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << 1000 * double(clock()) / CLOCKS_PER_SEC; #ifndef debug cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n"; #endif } }

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...