제출 #757280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757280		shjgkwo	Duathlon (APIO18_duathlon)	C++17	100 / 100	370 ms	66064 KiB

count_triplets

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>

using namespace std;

const int MAXN = 100010;

vector<int> edge[MAXN];

map<int, int> bcce[MAXN];
map<int, long long> bcm[MAXN];

int bcc_cnt = 0;

int pre_cnt = 0;
int pre[MAXN];
int low[MAXN];
int mypar[MAXN];
int myorigin[MAXN];
int is_sep[MAXN];

long long sum_perm_cnt = 0;
long long node_cnt[MAXN];
long long cached_node_sum[MAXN];

set<int> bcc_node[MAXN];

stack<pair<int, int> > st;

long long ans = 0;
long long xcnt = 0;

inline const long long nP3(long long n) {
    return n * (n - 1) * (n - 2);
}

inline const long long nP2(long long n) {
    return n * (n - 1);
}

void dfs(int origin, int u, int par) {
    int child = 0, flag = 0;
    xcnt++;
    mypar[u] = par;
    myorigin[u] = origin;
    node_cnt[u] = 1;
    low[u] = pre[u] = ++pre_cnt;
    for(auto &v: edge[u]) {
        if(v == par) continue;
        if(!pre[v]) {
            child++;
            st.push({u, v});
            dfs(origin, v, u);
            node_cnt[u] += node_cnt[v];
            cached_node_sum[u] += node_cnt[v];
            low[u] = min(low[u], low[v]);
            if(pre[u] <= low[v]) {
                bcc_cnt++;
                flag = 1;
                while(st.size() && (st.top().first != u || st.top().second != v)) {
                    int x = st.top().first;
                    int y = st.top().second;
                    bcc_node[bcc_cnt].insert(x);
                    bcc_node[bcc_cnt].insert(y);
                    bcce[x][y] = bcc_cnt;
                    bcce[y][x] = bcc_cnt;
                    if(mypar[y] == x) {
                        bcm[x][bcc_cnt] += node_cnt[y];
                    }
                    st.pop();
                }
                int x = st.top().first;
                int y = st.top().second;
                bcc_node[bcc_cnt].insert(x);
                bcc_node[bcc_cnt].insert(y);
                bcce[x][y] = bcc_cnt;
                bcce[y][x] = bcc_cnt;
                if(mypar[y] == x) {
                    bcm[x][bcc_cnt] += node_cnt[y];
                }
                st.pop();
            }
        }
        else if(pre[u] > pre[v]) {
            st.push({u, v});
            low[u] = min(low[u], pre[v]);
        }
    }
    if(child >= 2 && par == 0) is_sep[u] = 1;
    else if(flag && par != 0) is_sep[u] = 1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        if (pre[i]) {
            continue;
        }
        xcnt = 0;
        dfs(i, i, 0);
        ans += nP3(xcnt);
    }
    for (int i = 1; i <= bcc_cnt; i++) {
        for(auto &u: bcc_node[i]) {
            long long node_sum = 0;
            if (!bcc_node[i].count(mypar[u])) {
                node_sum += node_cnt[myorigin[u]] - node_cnt[u];
            }
            node_sum += cached_node_sum[u];
            if (bcm[u].count(i)) {
                node_sum -= bcm[u][i];
            }
            ans -= nP2(node_sum + 1) * (bcc_node[i].size() - 1);
        }
    }
    cout << ans << "\n";
    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