oj.uz

Submission #618528

# Submission time Handle Problem Language Result Execution time Memory
618528 2022-08-02T05:18:52 Z Do_you_copy Toll (APIO13_toll) C++17
56 / 100
 3 ms 468 KB 
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i < r; ++i)
using namespace std;
typedef long long ll;

const int N = 1e5, M = 3e5, K = 20;

struct Edge {
	int x, y, w;
	bool operator<(const Edge& o) const
	{
		return w < o.w;
	}
} E[K+M];

int f[N+1], rk[N+1];

int F(int x)
{
	return f[x] ? f[x] = F(f[x]) : x;
}

inline void reset(int n)
{
	fill_n(f+1, n, 0);
	fill_n(rk+1, n, 0);
}

inline void merge(int rx, int ry)
{
	if (rx == ry) return;
	if (rk[rx] < rk[ry]) swap(rx, ry);
	f[ry] = rx;
	rk[rx] += rk[rx] == rk[ry];
}

void kruskal(int n, int l, int r, int ans[])
{
	int c = 0;
	reset(n);
	rep (i, l, r) {
		int x = F(E[i].x), y = F(E[i].y);
		if (x != y) {
			merge(x, y);
			ans[c++] = i;
			if (c == n-1) break;
		}
	}
}

int n, m, k, cnt, id[N+1], p[N+1], adj[K+2], dep[K+2], fa[K+2];
ll sum[K+2], ss[K+2];
bool b[K+2], used[2*K];

struct List {
	int to, nxt;
	bool b;
} L[2*K+1];

int ptr = 1;
inline void add(int x, int y, bool b)
{
	L[ptr] = (List){y, adj[x], b};
	adj[x] = ptr++;
}

void dfs(int u, int p)
{
	ss[u] = sum[u];
	for (int i = adj[u]; i; i = L[i].nxt) {
		int v = L[i].to;
		if (v == p) continue;
		dep[v] = dep[u] + 1;
		fa[v] = u;
		b[v] = L[i].b;
		dfs(v, u);
		ss[u] += ss[v];
	}
}

inline void update(int& x, int w, ll& ans)
{
	if (!b[x]) return;
	//cerr << w << " " << ss[x] << "\n";
	ans += w * ss[x];
	b[x] = false;
}

ll cal(int s)
{
	ptr = 1;
	fill_n(adj+1, cnt, 0);

	reset(cnt);

	rep (i, 0, k) if (s & (1<<i)) {
		int x = E[i].x, y = E[i].y, rx = F(x), ry = F(y);
		if (rx == ry) return 0;
		add(x, y, true);
		add(y, x, true);
		merge(rx, ry);
	}

	rep (i, k, k+cnt-1) {
		int x = E[i].x, y = E[i].y, rx = F(x), ry = F(y);
		if (rx != ry) {
			add(x, y, false);
			add(y, x, false);
			merge(rx, ry);
			used[i] = false;
		} else {
			used[i] = true;
		}
	}

	dfs(1, 0);

	ll ans = 0;

	rep (i, k, k+cnt-1) if (used[i]) {
		int x = E[i].x, y = E[i].y, w = E[i].w;
		if (dep[y] < dep[x]) swap(x, y);
		while (dep[y] != dep[x]) {
			update(y, w, ans);
			y = fa[y];
		}
		while (x != y) {
			update(x, w, ans);
			update(y, w, ans);
			x = fa[x];
			y = fa[y];
		}
	}

	//cerr << s << " " << ans << "\n";
	return ans;
}

int main()
{
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        //freopen("test.ans", "w", stdout);
    }
	scanf("%d%d%d", &n, &m, &k);
	if (m >= 250000){
      cout << 0; return 0;
    }	
  rep (i, k, k+m)
		scanf("%d%d%d", &E[i].x, &E[i].y, &E[i].w);
	rep (i, 0, k)
		scanf("%d%d", &E[i].x, &E[i].y);
	rep (i, 1, n+1)
		scanf("%d", p+i);

	sort(E+k, E+k+m);

	static int v[N-1];
	kruskal(n, 0, k+m, v);

	reset(n);
	rep (i, 0, n-1) {
		if (v[i] >= k){
			merge(F(E[v[i]].x), F(E[v[i]].y));
		}
	}

	rep (i, 1, n+1) {
		int j = F(i);
		if (!id[j]) id[j] = ++cnt;
		sum[id[i] = id[j]] += p[i];
	}
	rep (i, 0, k+m) {
		E[i].x = id[E[i].x];
		E[i].y = id[E[i].y];
	}
	kruskal(cnt, k, k+m, v);

	rep (i, 0, cnt-1){
		E[k+i] = E[v[i]];
	}
	ll ans = 0;
	rep (s, 1, 1<<k)
		ans = max(ans, cal(s));

	printf("%lld\n", ans);
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   scanf("%d%d%d", &E[i].x, &E[i].y, &E[i].w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf("%d%d", &E[i].x, &E[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |   scanf("%d", p+i);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 2 ms 468 KB Output is correct

Subtask #4
0 / 22.0

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

Subtask #5
0 / 22.0

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