oj.uz

답안 #375655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375655 2021-03-09T16:15:15 Z rainboy 통행료 (APIO13_toll) C
100 / 100
 2490 ms 8212 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], rep[N]; long long sz[N];

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

int join(int i, int j, int h) {
	i = find(i);
	j = find(j);
	if (i == j) {
		type[h] = -1;
		return 0;
	}
	if (rep[i] != -1 && rep[j] != -1)
		type[h] = 1;
	if (ds[i] > ds[j]) {
		ds[i] = j;
		if (h != -1) {
			sz[j] += sz[i];
			if (rep[j] == -1)
				rep[j] = rep[i];
		}
	} else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
		if (h != -1) {
			sz[i] += sz[j];
			if (rep[i] == -1)
				rep[i] = rep[j];
		}
	}
	return 1;
}

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

int dd[N_], pp[N_], ff[N_]; long long aa[N];

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

	dd[i] = d, pp[i] = p, ff[i] = f, sz[i] = aa[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 hh[M];
	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("%lld", &aa[i]);
	sort(hh, 0, m);
	memcpy(sz, aa, n * sizeof *sz);
	for (h = 0; h < m; h++) {
		int h_ = hh[h];

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

		if (type[h_] == 0)
			join(ii[h_], jj[h_], h_);
		else if (type[h_] == 1)
			add(rep[find(ii[h_])], rep[find(jj[h_])], cc[h_]);
	}
	r = idx[rep[find(0)]];
	for (i = 0; i < n; i++)
		if (ds[i] < 0)
			aa[idx[rep[i]]] = sz[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], -1))
					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:130:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  130 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:132:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  132 |   scanf("%d%d%d", &ii[h], &jj[h], &cc[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:139:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  139 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
toll.c:144:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  144 |   scanf("%lld", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 4 ms 492 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 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 232 ms 8044 KB Output is correct
8 Correct 240 ms 8044 KB Output is correct
9 Correct 247 ms 8044 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 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 232 ms 8044 KB Output is correct
8 Correct 240 ms 8044 KB Output is correct
9 Correct 247 ms 8044 KB Output is correct
10 Correct 2106 ms 8212 KB Output is correct
11 Correct 2342 ms 8172 KB Output is correct
12 Correct 2490 ms 8084 KB Output is correct