Submission #356347

#	Time	Username	Problem	Language	Result	Execution time	Memory
356347		valerikk	철인 이종 경기 (APIO18_duathlon)	C++17	0 / 100	218 ms	30820 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 7;

int n, m;
vector<pair<int, int>> g[N];
vector<int> gr[N];
int dep[N], low[N];
bool vis[N];
int col[N], cnt;
int sz[N];
long long ans;
int S;

void dfs(int v, int p = -1) {
    low[v] = dep[v];
    vis[v] = true;
    for (auto [u, i] : g[v]) {
        if (!vis[u]) {
            dep[u] = dep[v] + 1;
            dfs(u, i);
            low[v] = min(low[v], low[u]);
        } else {
            if (i != p)
                low[v] = min(low[v], dep[u]);
        }
    }
}

void paint(int v, int p = -1) {
    vis[v] = true;
    for (auto [u, i] : g[v]) {
        if (!vis[u]) {
            if (dep[v] <= low[u]) {
                col[i] = ++cnt;
            } else {
                col[i] = col[p];
            }
            paint(u, i);
        } else {
            if (i != p) {
                if (dep[u] < dep[v]) col[i] = col[p];
            }
        }
    }
}

int get_size(int v, int p = -1) {
    sz[v] = v <= n;
    for (int u : gr[v]) {
        if (u != p) {
            sz[v] += get_size(u, v);
        }
    }
    return sz[v];
}

void find_ans(int v, int p = -1) {
    vis[v] = true;
    for (int u : gr[v]) {
        if (u != p)
            find_ans(u, v);
    }
    if (v > n) {
        int sz_v = gr[v].size();
        ans += (long long)sz_v * (sz_v - 1) * (sz_v - 2);
        int cur_sum = 0;
        for (int u : gr[v]) {
            int sz_u = u == p ? S - sz[v] : sz[u];
            ans += (long long)sz_v * (sz_v - 1) * (sz_u - 1);
            ans += (long long)cur_sum * (sz_u - 1) * sz_v;
            cur_sum += sz_u - 1;
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dep[i] = 0;
            dfs(i);
        }
    }
    for (int i = 1; i <= n; ++i)
        vis[i] = false;
    cnt = n;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            paint(i);
        }
    }/*
    for (int i = 1; i <= m; ++i)
        cout << col[i] << " ";
    cout << endl;
    return 0;*/
    for (int i = 1; i <= n; ++i) {
        vector<int> v;
        for (auto [u, i] : g[i])
            v.push_back(col[i]);
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        for (int c : v) {
            // cout << min(i, c) << " " << max(i, c) << endl;
            gr[i].push_back(c);
            gr[c].push_back(i);
        }
    }
    for (int i = 1; i <= cnt; ++i)
        vis[i] = false;
    ans = 0;
    for (int i = 1; i <= cnt; ++i) {
        if (!vis[i]) {
            S = get_size(i);
            find_ans(i);
        }
    }
    cout << ans << endl;
    return 0;
}

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