Submission #757258

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757258	2023-06-12T21:42:11 Z	shjgkwo	Duathlon (APIO18_duathlon)	C++17	23 / 100	223 ms	53568 KB

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];

int bcc_cnt = 0;

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

long long sum_perm_cnt = 0;
long long node_cnt[MAXN];
long long p[MAXN * 2];

set<int> bcc_node[MAXN * 2];

stack<pair<int, int> > st;

long long ans = 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 u, int par) {
    int child = 0, flag = 0;
    mypar[u] = par;
    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(v, u);
            node_cnt[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;
                    st.pop();
                }
                if(st.size()) {
                    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;
                    st.pop();
                }
                ans += nP3(bcc_node[bcc_cnt].size());
                p[bcc_cnt] = nP2(bcc_node[bcc_cnt].size() - 1);
            }
        }
        else if(pre[u] > pre[v]) {
            st.push({u, v});
            low[u] = min(low[u], pre[v]);
        }
    }
    if(child >= 2 && par == -1) is_sep[u] = 1;
    else if(flag && par != -1) is_sep[u] = 1;
}

int chk[MAXN];

void solve(int origin, int u, int par) {
    long long sum_node_cnt = node_cnt[origin] - node_cnt[u];
    chk[u] = 1;
    long long sep = is_sep[u];

    for (auto &v: edge[u]) {
        if(chk[v]) continue;
        solve(origin, v, u);
        ans += sep * sum_node_cnt * node_cnt[v] * 2;
        sum_node_cnt += node_cnt[v];
    }
    
    if(!sep) {
        return;
    }

    for(auto &v: edge[u]) {
        if(par != v && mypar[v] != u) continue;
        int bcc = bcce[u][v];
        if(par != v) {
            ans += (node_cnt[1] - node_cnt[v] - 1) * p[bcc] * 2;
        }
        else {
            ans += (node_cnt[1] - node_cnt[u]) * p[bcc] * 2;
        }
    }
}

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;
        }
        dfs(i, 0);
    }
    for (int i = 1; i <= n; i++) {
        if (chk[i]) {
            continue;
        }
        solve(i, i, 0);
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	16724 KB	Output is correct
2	Correct	9 ms	16784 KB	Output is correct
3	Correct	9 ms	16724 KB	Output is correct
4	Correct	10 ms	16912 KB	Output is correct
5	Correct	11 ms	16748 KB	Output is correct
6	Correct	12 ms	16800 KB	Output is correct
7	Incorrect	8 ms	16724 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	16724 KB	Output is correct
2	Correct	9 ms	16784 KB	Output is correct
3	Correct	9 ms	16724 KB	Output is correct
4	Correct	10 ms	16912 KB	Output is correct
5	Correct	11 ms	16748 KB	Output is correct
6	Correct	12 ms	16800 KB	Output is correct
7	Incorrect	8 ms	16724 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	187 ms	53524 KB	Output is correct
2	Correct	200 ms	53568 KB	Output is correct
3	Correct	160 ms	48128 KB	Output is correct
4	Incorrect	162 ms	52232 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	16980 KB	Output is correct
2	Correct	10 ms	16980 KB	Output is correct
3	Correct	10 ms	16980 KB	Output is correct
4	Correct	14 ms	17108 KB	Output is correct
5	Correct	10 ms	17108 KB	Output is correct
6	Correct	11 ms	17108 KB	Output is correct
7	Correct	10 ms	17108 KB	Output is correct
8	Correct	10 ms	17108 KB	Output is correct
9	Correct	9 ms	16980 KB	Output is correct
10	Correct	10 ms	16980 KB	Output is correct
11	Correct	12 ms	17040 KB	Output is correct
12	Correct	11 ms	17040 KB	Output is correct
13	Correct	11 ms	17048 KB	Output is correct
14	Correct	10 ms	16980 KB	Output is correct
15	Correct	10 ms	16980 KB	Output is correct
16	Correct	9 ms	16852 KB	Output is correct
17	Correct	10 ms	16968 KB	Output is correct
18	Correct	9 ms	17044 KB	Output is correct
19	Correct	10 ms	16980 KB	Output is correct
20	Correct	9 ms	17040 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	42316 KB	Output is correct
2	Correct	149 ms	42188 KB	Output is correct
3	Correct	155 ms	42376 KB	Output is correct
4	Correct	191 ms	42188 KB	Output is correct
5	Correct	143 ms	42276 KB	Output is correct
6	Correct	156 ms	51532 KB	Output is correct
7	Correct	193 ms	48368 KB	Output is correct
8	Correct	166 ms	46976 KB	Output is correct
9	Correct	154 ms	45220 KB	Output is correct
10	Correct	143 ms	42184 KB	Output is correct
11	Correct	144 ms	43552 KB	Output is correct
12	Correct	167 ms	43672 KB	Output is correct
13	Correct	139 ms	43468 KB	Output is correct
14	Correct	144 ms	41304 KB	Output is correct
15	Correct	130 ms	39116 KB	Output is correct
16	Correct	71 ms	32216 KB	Output is correct
17	Correct	223 ms	43356 KB	Output is correct
18	Correct	185 ms	43488 KB	Output is correct
19	Correct	182 ms	43456 KB	Output is correct
20	Correct	186 ms	43492 KB	Output is correct

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	17056 KB	Output is correct
2	Correct	10 ms	17052 KB	Output is correct
3	Incorrect	9 ms	17028 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	135 ms	42188 KB	Output is correct
2	Correct	153 ms	42348 KB	Output is correct
3	Incorrect	156 ms	42900 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	16724 KB	Output is correct
2	Correct	9 ms	16784 KB	Output is correct
3	Correct	9 ms	16724 KB	Output is correct
4	Correct	10 ms	16912 KB	Output is correct
5	Correct	11 ms	16748 KB	Output is correct
6	Correct	12 ms	16800 KB	Output is correct
7	Incorrect	8 ms	16724 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	16724 KB	Output is correct
2	Correct	9 ms	16784 KB	Output is correct
3	Correct	9 ms	16724 KB	Output is correct
4	Correct	10 ms	16912 KB	Output is correct
5	Correct	11 ms	16748 KB	Output is correct
6	Correct	12 ms	16800 KB	Output is correct
7	Incorrect	8 ms	16724 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Submission #757258

Compilation message