oj.uz

답안 #375647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375647 2021-03-09T16:07:43 Z rainboy 통행료 (APIO13_toll) C
78 / 100
 2500 ms 8172 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], ds[i] = pp[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;

int find_(int i) {
	return ff[i] < k && !cc1[ff[i]] || ds[i] < 0 ? i : (ds[i] = find_(ds[i]));
}

void paint(int i, int j, int c) {
	while (1) {
		i = find_(i), j = find_(j);
		if (i == j)
			return;
		if (dd[i] > dd[j])
			cc1[ff[i]] = c, i = pp[i];
		else
			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 'find_':
toll.c:112:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  112 |  return ff[i] < k && !cc1[ff[i]] || ds[i] < 0 ? i : (ds[i] = find_(ds[i]));
      |         ~~~~~~~~~~^~~~~~~~~~~~~~
toll.c: In function 'main':
toll.c:133:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  133 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:135:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  135 |   scanf("%d%d%d", &ii[h], &jj[h], &cc[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:142:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  142 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
toll.c:147:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  147 |   scanf("%lld", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 243 ms 8044 KB Output is correct
8 Correct 290 ms 8172 KB Output is correct
9 Correct 244 ms 8172 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 243 ms 8044 KB Output is correct
8 Correct 290 ms 8172 KB Output is correct
9 Correct 244 ms 8172 KB Output is correct
10 Correct 2235 ms 8088 KB Output is correct
11 Execution timed out 2569 ms 8044 KB Time limit exceeded
12 Halted 0 ms 0 KB -