oj.uz

답안 #375644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375644 2021-03-09T15:59:17 Z rainboy 통행료 (APIO13_toll) C
100 / 100
 2500 ms 14700 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 5 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 5 ms 492 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 264 ms 14548 KB Output is correct
8 Correct 245 ms 14444 KB Output is correct
9 Correct 252 ms 14548 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 5 ms 492 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 264 ms 14548 KB Output is correct
8 Correct 245 ms 14444 KB Output is correct
9 Correct 252 ms 14548 KB Output is correct
10 Correct 2215 ms 14556 KB Output is correct
11 Correct 2487 ms 14700 KB Output is correct
12 Correct 2500 ms 14572 KB Output is correct