oj.uz

Submission #975419

# Submission time Handle Problem Language Result Execution time Memory
975419 2024-05-05T06:29:06 Z dubabuba Duathlon (APIO18_duathlon) C++14
0 / 100
 127 ms 53700 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[u] * chi[u];
		sum_kv[u] += chi[v];

		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;

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

	// cout << u << "+ " << t << 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) {
	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;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from count_triplets.cpp:1:
count_triplets.cpp: In function 'void build()':
count_triplets.cpp:81:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |  assert(cyc_node.size() == n);
      |         ~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 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 14 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 84 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 Runtime error 15 ms 29528 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 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 14 ms 29272 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -