Submission #370845

#	Time	Username	Problem	Language	Result	Execution time	Memory
370845		LucaDantas	Duathlon (APIO18_duathlon)	C++17	31 / 100	268 ms	62572 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

constexpr int maxn = 3e5+10;

struct DSU
{
	int pai[maxn], peso[maxn];
	DSU() {for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1;}
	int find(int x) { return pai[x]==x?x:pai[x]=find(pai[x]); }
	void join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(peso[a] < peso[b])
			swap(a, b);
		pai[b] = a;
		peso[a] += peso[b];
	}
	int sz(int a) { return peso[find(a)]; }
	void add_sz(int a) { ++peso[find(a)]; }
} dsu;

int n, m;

vector<int> g[maxn];

int mark[2*maxn], low[maxn], depth[maxn];

vector<int> cut[maxn], tree[2*maxn];

vector<int> here;

void dfs1(int u) {
	mark[u] = 1;
	here.pb(u);
	for(int v : g[u]) {
		if(mark[v]) low[u] = min(low[u], depth[v]);
		else {
			depth[v] = depth[u] + 1;
			dfs1(v);
			low[u] = min(low[u], low[v]);
			// printf("(%d %d) %d %d\n", u, v, low[v], depth[u]);
			if(low[v] < depth[u]) dsu.join(u, v);
			else cut[u].pb(dsu.find(v));
		}
	}
}

void dfs2(int u) {
	mark[u] = 1;
	for(int v : g[u])
		if(!mark[v]) dfs2(v);
	if(!cut[u].size()) return;
	int fam = dsu.find(u);
	if(u != 1) {
		tree[u+n].pb(fam);
		tree[fam].pb(u+n);
	}
	for(int v : cut[u]) {
		dsu.add_sz(v);
		tree[u+n].pb(v);
		tree[v].pb(u+n);
	}
}

long long ans = 0, dp[maxn][4];

void dfs3(int u, int p) {
	// printf("%d %d\n", u, p);
	bool b = u<=n?1:0; // 1 -> block, 0 -> cut
	if(b) {
		// printf("b %d %d %d\n", u, dsu.sz(u), p);
		for(int v : tree[u]) {
			if(v != p) {
				dfs3(v, u);
				dp[u][1] += dp[v][1];
				dp[u][2] += dp[v][2];
				dp[u][3] += dp[v][2];
			}
		}
		int tam = dsu.sz(u) - 1;
		dp[u][2] += tam * dp[u][1] + max(0ll, 1ll * tam * (tam-1));
		dp[u][3] += tam * dp[u][1];
		dp[u][1] += tam;
		// printf("%d %lld %lld %lld\n", u, dp[u][1], dp[u][2], dp[u][3]);
	} else {
		// printf("c %d %d\n", u, p);
		mark[u] = 1;
		// printf("cut %d == ", u-n);
		// for(int v : tree[u])
		// 	printf("(%d %d) ", v, dsu.sz(v));
		// printf("\n");
		for(int v : tree[u]) {
			if(v != p) {
				dfs3(v, u);
				ans += 2 * dp[v][3]; // escolho eu e mais
				ans += 2 * dp[u][1] * dp[v][1];
				ans += 2 * dp[u][1] * dp[v][2];
				ans += 2 * dp[u][2] * dp[v][1];
				dp[u][2] += dp[v][2];
				// dp[u][2] += dp[u][1] * dp[v][1] + dp[v][2];
				dp[u][1] += dp[v][1];
				// printf("%d %lld %lld\n", u, dp[u][1], dp[u][2]);
			}
		}
		// printf("%d %lld %lld\n", u, dp[u][1], dp[u][2]);
	}
	// printf("%d %lld %lld\n", u, dp[u][1], dp[u][2]);
}

void root(int u) {
	mark[u] = 1; here = {u};
	for(int v : g[u])
		if(!mark[v]) depth[v] = 1 , dfs1(v), cut[u].pb(dsu.find(v));
	if(cut[u].size() == 1)
		dsu.join(cut[u][0], u), cut[u].clear();
	for(int x : here)
		mark[x] = 0;
	dfs2(u);
	for(int x : here)
		mark[x] = 1;
	here.clear();
}

void root_ans(int u) {
	// for(int v : tree[u])
	// 	dfs3(v, u);
	dfs3(u, 0);
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0, a, b; i < m; i++)
		scanf("%d %d", &a, &b), g[a].pb(b), g[b].pb(a);
	for(int i = 0; i < maxn; i++)
		low[i] = maxn;
	for(int i = 1; i <= n; i++)
		if(!mark[i]) root(i);
	auto choose3 = [](int a) {
		if(a < 3) return 0ll;
		return (1ll * a * (a-1) * (a-2));
	};
	for(int i = 1; i <= n; i++)
		if(i == dsu.find(i)) ans += choose3(dsu.sz(i));
	for(int i = n+1; i <= 2*n; i++)
		if(!mark[i] && tree[i].size()) root_ans(i);
	printf("%lld\n", ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |   scanf("%d %d", &a, &b), g[a].pb(b), g[b].pb(a);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• 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