oj.uz

Submission #370845

# Submission time Handle Problem Language Result Execution time Memory
370845 2021-02-24T18:31:44 Z LucaDantas Duathlon (APIO18_duathlon) C++17
31 / 100
 268 ms 62572 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, 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32108 KB Output is correct
2 Correct 22 ms 31980 KB Output is correct
3 Correct 22 ms 31980 KB Output is correct
4 Correct 22 ms 31980 KB Output is correct
5 Correct 22 ms 31980 KB Output is correct
6 Correct 22 ms 31980 KB Output is correct
7 Incorrect 22 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 22 ms 32108 KB Output is correct
2 Correct 22 ms 31980 KB Output is correct
3 Correct 22 ms 31980 KB Output is correct
4 Correct 22 ms 31980 KB Output is correct
5 Correct 22 ms 31980 KB Output is correct
6 Correct 22 ms 31980 KB Output is correct
7 Incorrect 22 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 129 ms 53740 KB Output is correct
2 Correct 135 ms 53992 KB Output is correct
3 Correct 182 ms 56580 KB Output is correct
4 Correct 156 ms 58468 KB Output is correct
5 Correct 159 ms 51952 KB Output is correct
6 Correct 182 ms 54768 KB Output is correct
7 Correct 191 ms 52332 KB Output is correct
8 Correct 227 ms 53608 KB Output is correct
9 Correct 187 ms 50540 KB Output is correct
10 Correct 164 ms 51052 KB Output is correct
11 Correct 132 ms 46376 KB Output is correct
12 Correct 124 ms 46316 KB Output is correct
13 Correct 113 ms 45804 KB Output is correct
14 Correct 109 ms 45804 KB Output is correct
15 Correct 89 ms 44396 KB Output is correct
16 Correct 91 ms 44364 KB Output is correct
17 Correct 26 ms 32748 KB Output is correct
18 Correct 25 ms 32748 KB Output is correct
19 Correct 25 ms 32748 KB Output is correct
20 Correct 25 ms 32748 KB Output is correct
21 Correct 25 ms 32748 KB Output is correct
22 Correct 25 ms 32768 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32236 KB Output is correct
2 Correct 23 ms 32236 KB Output is correct
3 Correct 23 ms 32236 KB Output is correct
4 Correct 23 ms 32364 KB Output is correct
5 Correct 23 ms 32364 KB Output is correct
6 Correct 23 ms 32256 KB Output is correct
7 Correct 22 ms 32364 KB Output is correct
8 Correct 23 ms 32236 KB Output is correct
9 Correct 22 ms 32236 KB Output is correct
10 Correct 23 ms 32236 KB Output is correct
11 Correct 23 ms 32236 KB Output is correct
12 Correct 23 ms 32236 KB Output is correct
13 Correct 22 ms 32236 KB Output is correct
14 Correct 26 ms 32236 KB Output is correct
15 Correct 26 ms 32384 KB Output is correct
16 Correct 23 ms 32108 KB Output is correct
17 Correct 22 ms 32252 KB Output is correct
18 Correct 23 ms 32236 KB Output is correct
19 Correct 22 ms 32236 KB Output is correct
20 Correct 22 ms 32236 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 49508 KB Output is correct
2 Correct 194 ms 49636 KB Output is correct
3 Correct 183 ms 49508 KB Output is correct
4 Correct 184 ms 49508 KB Output is correct
5 Correct 174 ms 49508 KB Output is correct
6 Correct 209 ms 62572 KB Output is correct
7 Correct 238 ms 57700 KB Output is correct
8 Correct 268 ms 56836 KB Output is correct
9 Correct 197 ms 54500 KB Output is correct
10 Correct 205 ms 49640 KB Output is correct
11 Correct 184 ms 49636 KB Output is correct
12 Correct 175 ms 49388 KB Output is correct
13 Correct 223 ms 49388 KB Output is correct
14 Correct 167 ms 48808 KB Output is correct
15 Correct 149 ms 48236 KB Output is correct
16 Correct 95 ms 45164 KB Output is correct
17 Correct 107 ms 44132 KB Output is correct
18 Correct 93 ms 43916 KB Output is correct
19 Correct 95 ms 44196 KB Output is correct
20 Correct 103 ms 44052 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 32236 KB Output is correct
2 Correct 22 ms 32236 KB Output is correct
3 Incorrect 22 ms 32236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 49644 KB Output is correct
2 Correct 244 ms 50148 KB Output is correct
3 Incorrect 184 ms 49476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 32108 KB Output is correct
2 Correct 22 ms 31980 KB Output is correct
3 Correct 22 ms 31980 KB Output is correct
4 Correct 22 ms 31980 KB Output is correct
5 Correct 22 ms 31980 KB Output is correct
6 Correct 22 ms 31980 KB Output is correct
7 Incorrect 22 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 22 ms 32108 KB Output is correct
2 Correct 22 ms 31980 KB Output is correct
3 Correct 22 ms 31980 KB Output is correct
4 Correct 22 ms 31980 KB Output is correct
5 Correct 22 ms 31980 KB Output is correct
6 Correct 22 ms 31980 KB Output is correct
7 Incorrect 22 ms 31980 KB Output isn't correct
8 Halted 0 ms 0 KB -