oj.uz

Submission #975428

# Submission time Handle Problem Language Result Execution time Memory
975428 2024-05-05T06:38:58 Z dubabuba Duathlon (APIO18_duathlon) C++14
0 / 100
 136 ms 53188 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

template<typename T> pair<T, T> SP(T L, T R) { return MP(min(L, R), max(L, R)); }
template<typename T> void ono_min(T &MIN, T CMP) { if(MIN > CMP) MIN = CMP; }
template<typename T> void ono_max(T &MAX, T CMP) { if(MAX < CMP) MAX = CMP; }
const int mxn = 2e5 + 10;

vector<int> adj[mxn];
vector<pii> edges;

int vis[mxn], low[mxn];
int n, m, TIME;

void dfs(int u, int p) {
	TIME++;
	vis[u] = TIME;
	low[u] = TIME;
	for(int v : adj[u]) {
		if(v == p) continue;
		if(vis[v] == 0) dfs(v, u);
		ono_min(low[u], low[v]);
	}
}

vector<int> cyc_node;
vector<int> cyc_edge[mxn];
int col[mxn], cnt[mxn];

int colour(int u) {
	if(col[u] < 0) return u;
	return col[u] = colour(col[u]);
}

bool unite(int u, int v) {
	u = colour(u);
	v = colour(v);
	if(u == v) return 0;

	if(col[u] > col[v]) swap(u, v);
	col[u] += col[v];
	col[v] = u;
	return 1;
}

void build() {
	for(int i = 1; i <= n; i++) {
		if(vis[i] == 0)
			dfs(i, i);
	}

	for(int i = 1; i <= n; i++) {
		col[low[i]]--;
		cnt[low[i]]++;
		if(low[i] == i)
			cyc_node.push_back(i);
	}

	set<pii> s;
	for(pii p : edges) {
		int u = low[p.ff];
		int v = low[p.ss];
		if(u == v) continue;
		s.insert(SP(u, v));
		unite(u, v);
	}

	for(pii p : s) {
		int u = p.ff;
		int v = p.ss;
		cyc_edge[u].push_back(v);
		cyc_edge[v].push_back(u);
	}

	// assert(cyc_node.size() == n);
}

int chi[mxn];
i64 kv_sum[mxn];
i64 sum_kv[mxn];
i64 ans = 0;

void dfs_solve(int u, int p) {
	vis[u] = 1;
	for(int v : cyc_edge[u]) {
		if(p == v) continue;
		if(vis[v]) continue;
		dfs_solve(v, u);

		chi[u] += chi[v];
		kv_sum[u] += 1LL * chi[v] * chi[v];
		sum_kv[u] += chi[v];

		if(cnt[u] > 1)
			ans += 1LL * (cnt[u] - 1) * cnt[v] * 2;
		if(cnt[u] > 2)
			ans += 1LL * (cnt[u] - 2) * (cnt[u] - 3) * cnt[v] * 2;
		// cout << u << "+ " << (cnt[u] - 1) * cnt[v] * 2 << endl;
	}

	sum_kv[u] = sum_kv[u] * sum_kv[u];
	assert(cnt[u] == 1);
	chi[u] += cnt[u];

	i64 t = sum_kv[u] - kv_sum[u];
	ans += t;

	i64 total = -col[colour(u)];
	i64 UP = total - chi[u];
	i64 DO = chi[u] - cnt[u];
	ans += UP * DO * 2;

	if(cnt[u] > 1)
		ans += UP * (cnt[u] - 1) * 2;
	if(cnt[u] > 2)
		ans += UP * (cnt[u] - 1) * (cnt[u] - 2) * 2;

	// cout << u << "+ " << sum_kv[u] << ' ' << kv_sum[u] << endl;
	// cout << u << "+ " << UP * DO * 2 << endl;
	// cout << u << "+ " << UP * (cnt[u] - 1) * 2 << endl;
	// cout << u << "+ " << UP * (cnt[u] - 1) * (cnt[u] - 2) * 2 << endl;
}

i64 nc(i64 a) {
	if(a < (i64) 4) return 0;
	return a * (a - 1) * (a - 2);
}

void solve() {
	memset(vis, 0, sizeof vis);
	for(int u : cyc_node) {
		if(vis[u] == 0)
			dfs_solve(u, u);
		ans += nc(cnt[u]);
	}
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back(SP(u, v));
	}

	build();
	solve();

	cout << ans << endl;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 29272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 29272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 53188 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14684 KB Output is correct
2 Correct 4 ms 14660 KB Output is correct
3 Correct 6 ms 14684 KB Output is correct
4 Correct 4 ms 14684 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 5 ms 14680 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 4 ms 14932 KB Output is correct
9 Correct 4 ms 14936 KB Output is correct
10 Correct 5 ms 14660 KB Output is correct
11 Incorrect 4 ms 14680 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 27848 KB Output is correct
2 Correct 105 ms 29120 KB Output is correct
3 Correct 132 ms 29120 KB Output is correct
4 Correct 104 ms 29116 KB Output is correct
5 Correct 105 ms 29124 KB Output is correct
6 Correct 105 ms 33984 KB Output is correct
7 Correct 105 ms 32368 KB Output is correct
8 Correct 105 ms 31416 KB Output is correct
9 Correct 136 ms 30660 KB Output is correct
10 Incorrect 123 ms 28668 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Runtime error 15 ms 29596 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 27848 KB Output is correct
2 Correct 104 ms 29120 KB Output is correct
3 Runtime error 109 ms 49604 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 29272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 29272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -