| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 375661 |
2021-03-09T16:21:59 Z |
rainboy |
Toll (APIO13_toll) |
C |
|
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];
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) {
int tmp, f;
if (dd[i] < dd[j])
tmp = i, i = j, j = tmp;
while (dd[i] > dd[j]) {
f = ff[i];
if (f < k && !cc1[f])
cc1[f] = c;
i = pp[i];
}
while (i != j) {
f = ff[i];
if (f < k && !cc1[f])
cc1[f] = c;
i = pp[i];
f = ff[j];
if (f < k && !cc1[f])
cc1[f] = 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:140:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
140 | scanf("%d%d%d", &n, &m, &k);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:142:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
142 | scanf("%d%d%d", &ii[h], &jj[h], &cc[h]), ii[h]--, jj[h]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:149:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
149 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
toll.c:154:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
154 | scanf("%lld", &aa[i]);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 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 |
248 ms |
8044 KB |
Output is correct |
| 8 |
Correct |
274 ms |
8044 KB |
Output is correct |
| 9 |
Correct |
250 ms |
8044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 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 |
248 ms |
8044 KB |
Output is correct |
| 8 |
Correct |
274 ms |
8044 KB |
Output is correct |
| 9 |
Correct |
250 ms |
8044 KB |
Output is correct |
| 10 |
Correct |
2126 ms |
8088 KB |
Output is correct |
| 11 |
Correct |
2306 ms |
8084 KB |
Output is correct |
| 12 |
Execution timed out |
2572 ms |
8172 KB |
Time limit exceeded |
