oj.uz

답안 #375652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375652 2021-03-09T16:13:20 Z rainboy 통행료 (APIO13_toll) C
78 / 100
 2500 ms 8180 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;
}

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

void dfs(char p, char f, char i, char 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(char i, char 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;
		char 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 'dfs':
toll.c:98:4: warning: array subscript has type 'char' [-Wchar-subscripts]
   98 |  dd[i] = d, pp[i] = p, ff[i] = f, sz[i] = aa[i];
      |    ^
toll.c:98:15: warning: array subscript has type 'char' [-Wchar-subscripts]
   98 |  dd[i] = d, pp[i] = p, ff[i] = f, sz[i] = aa[i];
      |               ^
toll.c:98:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   98 |  dd[i] = d, pp[i] = p, ff[i] = f, sz[i] = aa[i];
      |                          ^
toll.c:98:37: warning: array subscript has type 'char' [-Wchar-subscripts]
   98 |  dd[i] = d, pp[i] = p, ff[i] = f, sz[i] = aa[i];
      |                                     ^
toll.c:98:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   98 |  dd[i] = d, pp[i] = p, ff[i] = f, sz[i] = aa[i];
      |                                             ^
toll.c:99:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   99 |  for (o = eo[i]; o--; ) {
      |             ^
toll.c:100:13: warning: array subscript has type 'char' [-Wchar-subscripts]
  100 |   int h = eh[i][o], j = i ^ ii_[h] ^ jj_[h];
      |             ^
toll.c:104:6: warning: array subscript has type 'char' [-Wchar-subscripts]
  104 |    sz[i] += sz[j];
      |      ^
toll.c: In function 'paint':
toll.c:113:9: warning: array subscript has type 'char' [-Wchar-subscripts]
  113 |   if (dd[i] > dd[j]) {
      |         ^
toll.c:113:17: warning: array subscript has type 'char' [-Wchar-subscripts]
  113 |   if (dd[i] > dd[j]) {
      |                 ^
toll.c:114:10: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |    if (ff[i] < k && !cc1[ff[i]])
      |          ^
toll.c:114:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |    if (ff[i] < k && !cc1[ff[i]])
      |                            ^
toll.c:114:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |    if (ff[i] < k && !cc1[ff[i]])
      |                          ~~^~~
toll.c:115:11: warning: array subscript has type 'char' [-Wchar-subscripts]
  115 |     cc1[ff[i]] = c;
      |           ^
toll.c:115:11: warning: array subscript has type 'char' [-Wchar-subscripts]
  115 |     cc1[ff[i]] = c;
      |         ~~^~~
toll.c:116:10: warning: array subscript has type 'char' [-Wchar-subscripts]
  116 |    i = pp[i];
      |          ^
toll.c:118:10: warning: array subscript has type 'char' [-Wchar-subscripts]
  118 |    if (ff[j] < k && !cc1[ff[j]])
      |          ^
toll.c:118:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  118 |    if (ff[j] < k && !cc1[ff[j]])
      |                            ^
toll.c:118:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  118 |    if (ff[j] < k && !cc1[ff[j]])
      |                          ~~^~~
toll.c:119:11: warning: array subscript has type 'char' [-Wchar-subscripts]
  119 |     cc1[ff[j]] = c;
      |           ^
toll.c:119:11: warning: array subscript has type 'char' [-Wchar-subscripts]
  119 |     cc1[ff[j]] = c;
      |         ~~^~~
toll.c:120:10: warning: array subscript has type 'char' [-Wchar-subscripts]
  120 |    j = pp[j];
      |          ^
toll.c: In function 'main':
toll.c:197:19: warning: array subscript has type 'char' [-Wchar-subscripts]
  197 |     cost += cc1[ff[i]] * sz[i];
      |                 ~~^~~
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 1 ms 388 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 388 KB Output is correct
3 Correct 2 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 3 ms 492 KB Output is correct
7 Correct 249 ms 8180 KB Output is correct
8 Correct 232 ms 8044 KB Output is correct
9 Correct 232 ms 8172 KB Output is correct
10 Correct 2172 ms 8088 KB Output is correct
11 Correct 2393 ms 8004 KB Output is correct
12 Execution timed out 2561 ms 8084 KB Time limit exceeded