oj.uz

답안 #375649

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375649 2021-03-09T16:09:42 Z rainboy 통행료 (APIO13_toll) C
100 / 100
 2457 ms 8088 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
toll.c:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
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 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 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 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 3 ms 492 KB Output is correct
7 Correct 233 ms 8044 KB Output is correct
8 Correct 238 ms 8084 KB Output is correct
9 Correct 240 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 3 ms 492 KB Output is correct
7 Correct 233 ms 8044 KB Output is correct
8 Correct 238 ms 8084 KB Output is correct
9 Correct 240 ms 8044 KB Output is correct
10 Correct 2087 ms 8088 KB Output is correct
11 Correct 2407 ms 8084 KB Output is correct
12 Correct 2457 ms 8084 KB Output is correct