Submission #579458

#	Time	Username	Problem	Language	Result	Execution time	Memory
579458		vovamr	Duathlon (APIO18_duathlon)	C++17	100 / 100	242 ms	61856 KiB

count_triplets

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC target("tune=native")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 4e5 + 10;
#define int long long

int n, m;
ve<int> gr[N];
ve<pii> g[N], g1[N];
int in[N], f[N], sz[N], used[N], used1[N], used2[N];
int tim = 0, num, ans;
ve<int> ar; deque<int> ord;

inline void dfs (int v, int p) {
        used[v] = 1;
        in[v] = f[v] = tim++;
        for (auto &[to, id] : g[v]) {
                if (to == p) continue;
                if (used[to]) {
                        chmin(f[v], in[to]);
                        if (in[to] < in[v]) g1[v].pb({to, id});
                }
                else {
                        if (!~p) { ord.pb(id); used1[id] = 1; }
                        dfs(to, v);
                        g1[v].pb({to, id});
                        chmin(f[v], f[to]);
                }
        }
}
inline void dfs1(int v) {
        if (used2[v]) return;
        used2[v] = 1;
        for (auto &[to, id] : g1[v]) {
                if (used1[id]) continue;
                used1[id] = 1;
                if (f[to] < in[v]) { ar.pb(id); dfs1(to); }
                else ord.pb(id);
        }
}
inline void dfssz(int v, int p) {
        used[v] = 1;
        if (v < n) sz[v] = 1;
        for (auto &to : gr[v]) {
                if (to == p) continue;
                dfssz(to, v); sz[v] += sz[to];
        }
}
inline void calc(int v, int p) {
        int up = num - sz[v];
        if (v >= n) {
                ans -= up * (up - 1) * (sz(gr[v]) - 1);
                for (auto &to : gr[v]) {
                        if (to == p) continue;
                        ans -= sz[to] * (sz[to] - 1) * (sz(gr[v]) - 1);
                }
        }
        for (auto &to : gr[v]) {
                if (to == p) continue;
                calc(to, v);
        }
}

inline void solve() {
        cin >> n >> m;
        ve<pii> e(m);
        for (int i = 0; i < m; ++i) {
                int u, v;
                cin >> u >> v, --u; --v;
                g[u].pb({v, i}); g[v].pb({u, i});
                e[i] = mpp(v, u);
        }
        
        int cur = n;
        for (int i = 0; i < n; ++i) {
                if (used[i]) continue;
                int have = tim; dfs(i, -1);
                ans += (tim - have) * (tim - have - 1) * (tim - have - 2);
                
                while (sz(ord)) {
                        int j = ord.front();
                        ord.pop_front();
                        
                        ar.clear(); ar.pb(j);
                        dfs1(e[j].fi), dfs1(e[j].se);
                        
                        set <int> st;
                        for (auto &id : ar) {
                                st.insert(e[id].fi);
                                st.insert(e[id].se);
                        }
                        for (auto &v : st) {
                                gr[v].pb(cur);
                                gr[cur].pb(v);
                        } ++cur;
                }
        }
        
        fill(used, used + N, 0);
        for (int i = n; i < cur; ++i) {
                if (!used[i]) {
                        dfssz(i, -1);
                        num = sz[i];
                        calc(i, -1);
                }
        }
        
        cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10