oj.uz

Submission #370823

# Submission time Handle Problem Language Result Execution time Memory
370823 2021-02-24T17:19:43 Z LucaDantas Duathlon (APIO18_duathlon) C++17
8 / 100
 187 ms 58212 KB 
#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-n, 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[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]);
}

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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31980 KB Output is correct
2 Correct 21 ms 31980 KB Output is correct
3 Correct 20 ms 31980 KB Output is correct
4 Correct 21 ms 31980 KB Output is correct
5 Correct 20 ms 31980 KB Output is correct
6 Correct 20 ms 31980 KB Output is correct
7 Incorrect 20 ms 31980 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31980 KB Output is correct
2 Correct 21 ms 31980 KB Output is correct
3 Correct 20 ms 31980 KB Output is correct
4 Correct 21 ms 31980 KB Output is correct
5 Correct 20 ms 31980 KB Output is correct
6 Correct 20 ms 31980 KB Output is correct
7 Incorrect 20 ms 31980 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 53740 KB Output is correct
2 Correct 130 ms 53740 KB Output is correct
3 Correct 181 ms 56176 KB Output is correct
4 Correct 146 ms 58212 KB Output is correct
5 Correct 143 ms 51696 KB Output is correct
6 Correct 172 ms 54384 KB Output is correct
7 Correct 180 ms 51948 KB Output is correct
8 Correct 179 ms 53224 KB Output is correct
9 Correct 168 ms 50156 KB Output is correct
10 Correct 161 ms 50668 KB Output is correct
11 Correct 124 ms 46080 KB Output is correct
12 Correct 124 ms 45932 KB Output is correct
13 Correct 111 ms 45548 KB Output is correct
14 Correct 119 ms 45292 KB Output is correct
15 Correct 86 ms 44024 KB Output is correct
16 Correct 83 ms 44012 KB Output is correct
17 Correct 23 ms 32748 KB Output is correct
18 Correct 23 ms 32824 KB Output is correct
19 Correct 23 ms 32780 KB Output is correct
20 Correct 24 ms 32748 KB Output is correct
21 Correct 23 ms 32748 KB Output is correct
22 Correct 23 ms 32620 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 32236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 49540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 32236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 187 ms 49508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31980 KB Output is correct
2 Correct 21 ms 31980 KB Output is correct
3 Correct 20 ms 31980 KB Output is correct
4 Correct 21 ms 31980 KB Output is correct
5 Correct 20 ms 31980 KB Output is correct
6 Correct 20 ms 31980 KB Output is correct
7 Incorrect 20 ms 31980 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31980 KB Output is correct
2 Correct 21 ms 31980 KB Output is correct
3 Correct 20 ms 31980 KB Output is correct
4 Correct 21 ms 31980 KB Output is correct
5 Correct 20 ms 31980 KB Output is correct
6 Correct 20 ms 31980 KB Output is correct
7 Incorrect 20 ms 31980 KB Output isn't correct
8 Halted 0 ms 0 KB -