Submission #371145

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
371145	2021-02-25T23:12:34 Z	LucaDantas	Duathlon (APIO18_duathlon)	C++17	Compilation error	0 ms	0 KB

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], size = 0;

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

vector<int> here;

void dfs1(int u) {
	++size;
	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]);
			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]; // maneira de escolher 2 na msm subtree

int sz[maxn];

void rotate(int u, int v) {
	sz[u] -= sz[v];
	sz[v] += sz[u];
	if(u > n) {
		// u => cut, v => block
		dp[u] = (long long)sz[u] * (sz[u] - 1);
		dp[v] += dp[u];
	} else {
		dp[u] -= dp[v];
		dp[v] = (long long)sz[v] * (sz[v] - 1);
	}
}

void dfs4(int u, int p) {
	sz[u] += u<=n?dsu.sz(u)-(int)tree[u].size():1;
	for(int v : tree[u]) {
		if(v == p) continue;
		dfs4(v, u);
		sz[u] += sz[v];
		if(u<=n) dp[u] += dp[v];
	}
	if(u > n) dp[u] = (long long)sz[u] * (sz[u] - 1);
}

void dfs3(int u, int p) {
	bool b = u<=n?1:0; // 1 -> block, 0 -> cut
	if(b) {
		int tam = dsu.sz(u) - (int)tree[u].size();
		for(int v : tree[u])
			ans -= 1ll * tam * dp[v];
		for(int v : tree[u]) {
			if(v != p) {
				rotate(u, v);
				dfs3(v, u);
				rotate(v, u);
			}
		}
	} else {
		mark[u] = 1;
		for(int v : tree[u])
			ans -= dp[v];
		for(int v : tree[u]) {
			if(v != p) {
				rotate(u, v);
				dfs3(v, u);
				rotate(v, u);
			}
		}
	}
}

void root(int u) {
	mark[u] = 1; here = {u}; ++size;
	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); // comeco a dp no meu block
	for(int x : here)
		mark[x] = 1;
	here.clear();
}

void root_ans(int u) {
	dfs4(u, 0);
	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;
	auto choose3 = [](int a) {
		if(a < 3) return 0ll;
		return (1ll * a * (a-1) * (a-2));
	};
	for(int i = 1; i <= n; i++)
		if(!mark[i]) root(i), ans += choose3(size), size = 0;
	for(int i = n+1; i <= 2*n; i++)
		if(!mark[i] && tree[i].size()) root_ans(i);
	printf("%lld\n", ans);
}

Compilation message

count_triplets.cpp: In function 'void dfs1(int)':
count_triplets.cpp:36:4: error: reference to 'size' is ambiguous
   36 |  ++size;
      |    ^~~~
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from count_triplets.cpp:1:
/usr/include/c++/9/bits/range_access.h:252:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  252 |     size(const _Tp (&/*__array*/)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:242:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  242 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
count_triplets.cpp:29:43: note:                 'int size'
   29 | int mark[2*maxn], low[maxn], depth[maxn], size = 0;
      |                                           ^~~~
count_triplets.cpp: In function 'void root(int)':
count_triplets.cpp:124:29: error: reference to 'size' is ambiguous
  124 |  mark[u] = 1; here = {u}; ++size;
      |                             ^~~~
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from count_triplets.cpp:1:
/usr/include/c++/9/bits/range_access.h:252:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  252 |     size(const _Tp (&/*__array*/)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:242:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  242 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
count_triplets.cpp:29:43: note:                 'int size'
   29 | int mark[2*maxn], low[maxn], depth[maxn], size = 0;
      |                                           ^~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:153:40: error: reference to 'size' is ambiguous
  153 |   if(!mark[i]) root(i), ans += choose3(size), size = 0;
      |                                        ^~~~
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from count_triplets.cpp:1:
/usr/include/c++/9/bits/range_access.h:252:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  252 |     size(const _Tp (&/*__array*/)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:242:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  242 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
count_triplets.cpp:29:43: note:                 'int size'
   29 | int mark[2*maxn], low[maxn], depth[maxn], size = 0;
      |                                           ^~~~
count_triplets.cpp:153:47: error: reference to 'size' is ambiguous
  153 |   if(!mark[i]) root(i), ans += choose3(size), size = 0;
      |                                               ^~~~
In file included from /usr/include/c++/9/string:54,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from count_triplets.cpp:1:
/usr/include/c++/9/bits/range_access.h:252:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  252 |     size(const _Tp (&/*__array*/)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/9/bits/range_access.h:242:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  242 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
count_triplets.cpp:29:43: note:                 'int size'
   29 | int mark[2*maxn], low[maxn], depth[maxn], size = 0;
      |                                           ^~~~
count_triplets.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  143 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  145 |   scanf("%d %d", &a, &b), g[a].pb(b), g[b].pb(a);
      |   ~~~~~^~~~~~~~~~~~~~~~~