제출 #638323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638323		MohamedFaresNebili	Duathlon (APIO18_duathlon)	C++14	100 / 100	110 ms	32464 KiB

count_triplets

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

            using namespace std;
            using ll = long long;
            
            #define int ll

            const int MOD = 1e9 + 7;

            int N, M; bool vis[200005];
            int res, cur, BBC, S[200005];
            int timer, tin[200005], low[200005];
            vector<int> adj[200005], C[200005];
            vector<int> stck;

            void dfs(int v, int p) {
                tin[v] = low[v] = timer++; ++cur;
                vis[v] = 1; stck.push_back(v);
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    if(vis[u]) low[v] = min(low[v], tin[u]);
                    else {
                        dfs(u, v);
                        low[v] = min(low[v], low[u]);
                        if(low[u] >= tin[v]) {
                            C[v].push_back(N + ++BBC);
                            while(C[N + BBC].empty() || C[N + BBC].back() != u) {
                                C[N + BBC].push_back(stck.back());
                                stck.pop_back();
                            }
                        }
                    }
                }
            }
            void solve(int v) {
                S[v] = (v <= N);
                for(auto u : C[v]) {
                    solve(u); S[v] += S[u];
                    if(v > N) res -= C[v].size() * S[u] * (S[u] - 1ll);
                }
                if(v > N) res -= C[v].size() * (cur - S[v]) * (cur - S[v] - 1ll);
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M;
                for(int l = 0; l < M; l++) {
                    int U, V; cin >> U >> V;
                    adj[U].push_back(V);
                    adj[V].push_back(U);
                }
                for(int l = 1; l <= N; l++) {
                    if(vis[l]) continue;
                    cur = 0; dfs(l, l); solve(l);
                    res += cur * (cur - 1ll) * (cur - 2ll);
                }
                cout << res << "\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