Submission #630626

#	Time	Username	Problem	Language	Result	Execution time	Memory
630626		elkernos	Duathlon (APIO18_duathlon)	C++17	100 / 100	253 ms	46372 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int nax = 200123;

int n;

namespace {
int ti = 0;
vector<int> adj[nax], g[nax];
int disc[nax], low[nax], par[nax];
vector<vector<pair<int, int>>> fin;
int compsz[nax];
vector<pair<int, int>> st;
void add(int u, int v)
{
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
}
void add2(int u, int v)
{
    g[u].emplace_back(v);
    g[v].emplace_back(u);
}
void bccs(int u, bool root = 0)
{
    disc[u] = low[u] = ti++;
    int child = 0;
    for(int to : adj[u]) {
        if(to != par[u]) {
            if(disc[to] == -1) {
                child++;
                par[to] = u;
                st.emplace_back(u, to);
                bccs(to);
                low[u] = min(low[u], low[to]);
                if((root && child > 1) || (!root && disc[u] <= low[to])) {
                    vector<pair<int, int>> tmp;
                    while(st.back() != make_pair(u, to)) {
                        tmp.emplace_back(st.back());
                        st.pop_back();
                    }
                    tmp.emplace_back(st.back());
                    st.pop_back();
                    fin.emplace_back(tmp);
                }
            }
            else if(disc[to] < disc[u]) {
                low[u] = min(low[u], disc[to]);
                st.emplace_back(u, to);
            }
        }
    }
}
void work()
{
    for(int i = 1; i <= n; i++) {
        par[i] = disc[i] = low[i] = -1;
    }
    for(int i = 1; i <= n; i++) {
        if(disc[i] == -1) {
            bccs(i, 1);
            if(!st.empty()) {
                fin.emplace_back(st);
            }
            st.clear();
        }
    }
    int co = 0;
    for(auto a : fin) {
        set<int> s;
        for(auto b : a) {
            s.insert(b.first);
            s.insert(b.second);
        }
        co++;
        compsz[co] = (int)s.size();
        for(int i : s) {
            add2(i, n + co);
        }
    }
}
} // namespace

int ans;
int tot[nax];
bool vis[nax];

void dfs1(int u, int p)
{
    tot[u] = (u <= n);
    vis[u] = 1;
    for(int to : g[u]) {
        if(to == p) {
            continue;
        }
        dfs1(to, u);
        tot[u] += tot[to];
    }
}

void dfs2(int u, int p, int s)
{
    if(u <= n) {
        for(int to : g[u]) {
            assert(to > n);
            if(to == p) {
                continue;
            }
            ans -= (compsz[to - n] - 1) * (s - tot[to]) * (s - tot[to] - 1);
        }
        if(p != -1) {
            ans -= (compsz[p - n] - 1) * tot[u] * (tot[u] - 1);
        }
    }
    for(int to : g[u]) {
        if(to == p) {
            continue;
        }
        dfs2(to, u, s);
    }
}

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    work();
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            dfs1(i, -1);
            ans += tot[i] * (tot[i] - 1) * (tot[i] - 2);
            cerr << ans << '\n';
            dfs2(i, -1, tot[i]);
        }
    }
    cout << ans << '\n';
}

• 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