Submission #316517

#	Time	Username	Problem	Language	Result	Execution time	Memory
316517		Kevin_Zhang_TW	Duathlon (APIO18_duathlon)	C++17	31 / 100	175 ms	48248 KiB

count_triplets

#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() {cerr << endl;}
template<class T1, class ...T2>
void kout (T1 v, T2 ...e) { cerr << v << ' ', kout(e...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
#define int ll
int n, m, low[MAX_N], dep[MAX_N], g[MAX_N], bcc, sz[MAX_N], dfscnt;
vector<int> edge[MAX_N], be[MAX_N], child[MAX_N];
bool isap[MAX_N];
void dfs1(int x, int lst = -1) {
	++dfscnt;
	static stack<int> st;
	static int d;
	st.push(x);
	low[x] = dep[x] = ++d;
	for (int u : edge[x]) if (u != lst) {
		DE(x, u);
		if (!low[u]) {
			dfs1(u, x);
			low[x] = min(low[x], low[u]);
			if (low[u] >= dep[x]) {
				isap[x] = true;
				st.push(x);
				int gid = ++bcc + n;
				int tp = -1; do {
					tp = st.top(); st.pop();
					g[tp] = gid;
					child[gid].pb(tp);
					if (isap[tp]) {
						be[gid].pb(tp), be[tp].pb(gid);
						DE(tp, gid);
					}
				} while (tp != u);
			}
		}
		else low[x] = min(low[x], dep[u]);
	}
}
ll p2(ll v) { return v * (v-1); }
// count how many invalid triple there is
ll dfs2(int x, int m, int lst = -1) {
	ll res = 0;
	sz[x] = x <= n ? 1 : child[x].size();
	for (int u : be[x]) if (u != lst)
		res += dfs2(u, m, x), sz[x] += sz[u] - 1;
DE(x, sz[x]);

	if (x <= n) {
		ll all = p2(m-1);
		// way is the number of valid triples
		ll sum = m - sz[x], way = 0;
		for (int u : be[x]) if (u != lst) {
			way += (sz[u]-1) * sum * 2;
			sum += (sz[u]-1);
			ll cs = child[u].size() - 1;
			way += p2(cs);
		}
		if (lst != -1)
			way += p2(child[lst].size()-1);

		//DE(x, all, way);
		res += all - way;
	}
	else {
		ll mid = 0, upsz = m - sz[x] + 1;
		for (int u : child[x])
			if (!isap[u]) ++mid;
		for (int u : be[x]) if (u != lst) {
			res += p2(sz[u]) * mid;
		}
		res += p2(upsz) * mid;
	}
	DE(res);
	return res;
}
ll cal(int s) {
	dfscnt = 0;
	dfs1(s);
	ll m = dfscnt;
	return (m * (m-1) * (m-2)) - dfs2(s, m);
	//return 0;
}
signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0, a, b;i < m;++i) {
		cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	ll res = 0;
	for (int i = 1;i <= n;++i) 
		if (!dep[i])
			res += cal(i);
	cout << res << '\n';
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs1(ll, ll)':
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:29:3: note: in expansion of macro 'DE'
   29 |   DE(x, u);
      |   ^~
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:43:7: note: in expansion of macro 'DE'
   43 |       DE(tp, gid);
      |       ^~
count_triplets.cpp: In function 'll dfs2(ll, ll, ll)':
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:58:1: note: in expansion of macro 'DE'
   58 | DE(x, sz[x]);
      | ^~
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:85:2: note: in expansion of macro 'DE'
   85 |  DE(res);
      |  ^~

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