Submission #557980

#	Time	Username	Problem	Language	Result	Execution time	Memory
557980		nutella	Duathlon (APIO18_duathlon)	C++17	100 / 100	225 ms	38760 KiB

count_triplets

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
const int N = 100002, M = 200002;
const int mod = 998244353;
const ld eps = 1e-9;

vector<pair<int, int>> g[N];

vector<int> gr[N * 3];

int tin[N], fup[N], T = 0, n, m, last = 0, k, col[M], U[M], V[M], sz[N * 3], nn[N * 3];
int nww = 0;
bool used[N * 3];

ll ans = 0;

void precalc(int v, int p) {
    ++nww;
    used[v] = true;
    tin[v] = fup[v] = T++;
    for (auto [to, i]: g[v]) {
        if (to == p) continue;
        if (!used[to]) {
            precalc(to, v);
            ckmn(fup[v], fup[to]);
        } else {
            ckmn(fup[v], tin[to]);
        }
    }
}

void zhfs(int v, int j) {
    used[v] = true;
    for (auto [to, i]: g[v]) {
        if (i == j) continue;
        if (!used[to]) {
            if (j == -1 || fup[to] >= tin[v]) {
                col[i] = last++;
            } else {
                col[i] = col[j];
            }
            zhfs(to, i);
        } else if (tin[to] < tin[v]) {
            col[i] = col[j];
        }
    }
}

void dfs(int v, int p) {
    sz[v] = (v < n);
    used[v] = true;
    vector<int> a;
    for (int to: gr[v]) {
        if (!used[to]) {
            dfs(to, v);
            if (v >= n)
                a.pb(sz[to]);
            sz[v] += sz[to];
        }
    }
    if (v >= n) {
        if (p != -1) {
            a.pb(nww - sz[v]);
        }
        for (int i = 0; i < sz(a); ++i) {
            ans -= (sz(gr[v]) - 1) * 1LL * a[i] * (a[i] - 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        U[i] = a, V[i] = b;
        g[a].eb(b, i), g[b].eb(a, i);
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            nww = 0;
            precalc(i, -1);
            nn[i] = nww;
            ans += nww * 1LL * (nww - 1) * (nww - 2);
        }
    }
    memset(used, 0, sizeof(used));
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            zhfs(i, -1);
        }
    }
    for (int i = 0; i < m; ++i) {
        gr[col[i] + n].pb(U[i]), gr[col[i] + n].pb(V[i]);
        gr[U[i]].pb(col[i] + n);
        gr[V[i]].pb(col[i] + n);
    }
    k = n + last;
    for (int i = 0; i < k; ++i) {
        sort(all(gr[i]));
        uniq(gr[i]);
    }

    memset(used, 0, sizeof(used));
    for (int i = 0; i < k; ++i) {
        if (!used[i]) {
            nww = nn[i];
            dfs(i, -1);
        }
    }
    cout << ans;
    return 0;
}

• 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