Submission #434318

#	Time	Username	Problem	Language	Result	Execution time	Memory
434318		JerryLiu06	Duathlon (APIO18_duathlon)	C++17	0 / 100	134 ms	28288 KiB

count_triplets

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using db = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;
 
int N, M; vi adj[MX], BCC[3 * MX]; stack<int> stck; ll ans = 0;
 
int timer = 1; int in[MX], low[MX]; int numBCC = 1; ll SZ, sz[3 * MX];
 
// Generate Block-Cut Tree ~ O(N + M)
 
void DFS1(int X) {
    SZ++; in[X] = low[X] = timer++; stck.push(X);
 
    EACH(Y, adj[X]) {
        if (in[Y]) { low[X] = min(low[X], in[Y]); continue; }
 
        adj[Y].erase(find(all(adj[Y]), X)); DFS1(Y); low[X] = min(low[X], low[Y]);
 
        if (low[Y] >= in[X]) {
            int cur = N + numBCC; BCC[X].pb(cur);
 
            while (BCC[cur].empty() || BCC[cur].back() != Y) {
                BCC[cur].pb(stck.top()); stck.pop();
            }
            numBCC++;
        }
    }
}
void DFS2(int X) {
    sz[X] = (X <= N); EACH(Y, BCC[X]) {
        DFS2(Y); sz[X] += sz[Y]; if (X > N) ans -= sz(BCC[X]) * sz[Y] * (sz[Y] - 1);
    }
    if (X > N) ans -= sz(BCC[X]) * (N - sz[X]) * (N - sz[X] - 1);
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> N >> M; F0R(i, M) { int A, B; cin >> A >> B; adj[A].pb(B), adj[B].pb(A); }
 
    FOR(i, 1, N + 1) if (!in[i]) { SZ = 0; DFS1(i); ans += SZ * (SZ - 1) * (SZ - 2); DFS2(i); } cout << ans;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:38:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   38 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                      ^~~
count_triplets.cpp:84:5: note: in expansion of macro 'FOR'
   84 |     FOR(i, 1, N + 1) if (!in[i]) { SZ = 0; DFS1(i); ans += SZ * (SZ - 1) * (SZ - 2); DFS2(i); } cout << ans;
      |     ^~~
count_triplets.cpp:84:97: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   84 |     FOR(i, 1, N + 1) if (!in[i]) { SZ = 0; DFS1(i); ans += SZ * (SZ - 1) * (SZ - 2); DFS2(i); } cout << ans;
      |                                                                                                 ^~~~

• 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