Submission #375697

# Submission time Handle Problem Language Result Execution time Memory
375697 2021-03-09T17:06:31 Z rainboy Toll (APIO13_toll) C
100 / 100
2445 ms 7404 KB
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000
#define M	300000
#define K	20
#define N_	(K * 2)
#define M_	(K * 3)

long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int ii[M], jj[M], cc[M]; char type[M];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (cc[hh[j]] == cc[h])
				j++;
			else if (cc[hh[j]] < cc[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int idx[N];
int *eh[N_], eo[N_], n_;
int ii_[M_], jj_[M_], cc_[M_], m_;

void add(int i, int j, int c) {
	if (idx[i] == -1)
		idx[i] = n_++;
	if (idx[j] == -1)
		idx[j] = n_++;
	i = idx[i], j = idx[j];
	ii_[m_] = i, jj_[m_] = j, cc_[m_] = c, m_++;
	eo[i]++, eo[j]++;
}

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

void append(int i, int h) {
	eh[i][eo[i]++] = h;
}

int dd[N_], pp[N_], ff[N_]; long long bb[N_], sz[N_];

void dfs(int p, int f, int i, int d) {
	int o;

	dd[i] = d, pp[i] = p, ff[i] = f, sz[i] = bb[i];
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ii_[h] ^ jj_[h];

		if (j != p) {
			dfs(i, h, j, d + 1);
			sz[i] += sz[j];
		}
	}
}

int cc1[K], k;

void paint(int i, int j, int c) {
	while (i != j)
		if (dd[i] > dd[j]) {
			if (ff[i] < k && !cc1[ff[i]])
				cc1[ff[i]] = c;
			i = pp[i];
		} else {
			if (ff[j] < k && !cc1[ff[j]])
				cc1[ff[j]] = c;
			j = pp[j];
		}
}

int main() {
	static int aa[N], hh[M], rep[N];
	static char used[M_];
	int n, m, h, i, j, b, r;
	long long ans;

	scanf("%d%d%d", &n, &m, &k);
	for (h = 0; h < m; h++) {
		scanf("%d%d%d", &ii[h], &jj[h], &cc[h]), ii[h]--, jj[h]--;
		hh[h] = h;
	}
	memset(idx, -1, n * sizeof *idx);
	memset(ds, -1, n * sizeof *ds), memset(rep, -1, n * sizeof *rep);
	n_ = 0, m_ = 0;
	for (h = 0; h < k; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		rep[i] = i, rep[j] = j;
		add(i, j, 0);
	}
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	sort(hh, 0, m);
	for (h = 0; h < m; h++) {
		int h_ = hh[h];

		i = find(ii[h_]), j = find(jj[h_]);
		type[h_] = i == j ? -1 : rep[i] != -1 && rep[j] != -1;
		rep[i] = rep[j] = rep[i] != -1 ? rep[i] : rep[j];
		join(i, j);
	}
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		rep[i] = idx[i] != -1 ? i : -1;
	for (h = 0; h < m; h++) {
		int h_ = hh[h], i = find(ii[h_]), j = find(jj[h_]);

		if (type[h_] == 0) {
			rep[i] = rep[j] = rep[i] != -1 ? rep[i] : rep[j];
			join(i, j);
		} else if (type[h_] == 1)
			add(rep[i], rep[j], cc[h_]);
	}
	r = idx[rep[find(0)]];
	for (i = 0; i < n; i++)
		bb[idx[rep[find(i)]]] += aa[i];
	for (i = 0; i < n_; i++)
		eh[i] = (int *) malloc(eo[i] * sizeof *eh[i]), eo[i] = 0;
	ans = 0;
	for (b = 0; b < 1 << k; b++) {
		long long cost;
		int bad;

		memset(ds, -1, n_ * sizeof *ds);
		memset(eo, 0, n_ * sizeof *eo);
		memset(used, 0, m_ * sizeof *used);
		bad = 0;
		for (h = 0; h < m_; h++)
			if (h >= k || (b & 1 << h) != 0) {
				if (join(ii_[h], jj_[h]))
					append(ii_[h], h), append(jj_[h], h), used[h] = 1;
				else if (h < k) {
					bad = 1;
					break;
				}
			}
		if (bad)
			continue;
		dfs(-1, -1, r, 0);
		memset(cc1, 0, k * sizeof *cc1);
		for (h = k; h < m_; h++)
			if (!used[h])
				paint(ii_[h], jj_[h], cc_[h]);
		cost = 0;
		for (i = 0; i < n_; i++)
			if (ff[i] != -1 && ff[i] < k)
				cost += cc1[ff[i]] * sz[i];
		ans = max(ans, cost);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

toll.c: In function 'main':
toll.c:116:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  116 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:118:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  118 |   scanf("%d%d%d", &ii[h], &jj[h], &cc[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:125:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  125 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
toll.c:130:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  130 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 237 ms 7276 KB Output is correct
8 Correct 268 ms 7276 KB Output is correct
9 Correct 246 ms 7380 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 237 ms 7276 KB Output is correct
8 Correct 268 ms 7276 KB Output is correct
9 Correct 246 ms 7380 KB Output is correct
10 Correct 2036 ms 7404 KB Output is correct
11 Correct 2331 ms 7396 KB Output is correct
12 Correct 2445 ms 7292 KB Output is correct