| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 375697 |
2021-03-09T17:06:31 Z |
rainboy |
Toll (APIO13_toll) |
C |
|
2445 ms |
7404 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];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
void append(int i, int h) {
eh[i][eo[i]++] = h;
}
int dd[N_], pp[N_], ff[N_]; long long bb[N_], sz[N_];
void dfs(int p, int f, int i, int d) {
int o;
dd[i] = d, pp[i] = p, ff[i] = f, sz[i] = bb[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 aa[N], hh[M], rep[N];
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("%d", &aa[i]);
sort(hh, 0, m);
for (h = 0; h < m; h++) {
int h_ = hh[h];
i = find(ii[h_]), j = find(jj[h_]);
type[h_] = i == j ? -1 : rep[i] != -1 && rep[j] != -1;
rep[i] = rep[j] = rep[i] != -1 ? rep[i] : rep[j];
join(i, j);
}
memset(ds, -1, n * sizeof *ds);
for (i = 0; i < n; i++)
rep[i] = idx[i] != -1 ? i : -1;
for (h = 0; h < m; h++) {
int h_ = hh[h], i = find(ii[h_]), j = find(jj[h_]);
if (type[h_] == 0) {
rep[i] = rep[j] = rep[i] != -1 ? rep[i] : rep[j];
join(i, j);
} else if (type[h_] == 1)
add(rep[i], rep[j], cc[h_]);
}
r = idx[rep[find(0)]];
for (i = 0; i < n; i++)
bb[idx[rep[find(i)]]] += aa[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]))
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:116:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
116 | scanf("%d%d%d", &n, &m, &k);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:118:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
118 | scanf("%d%d%d", &ii[h], &jj[h], &cc[h]), ii[h]--, jj[h]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:125:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
125 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
toll.c:130:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
130 | scanf("%d", &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 |
2 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 |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
4 ms |
492 KB |
Output is correct |
| 6 |
Correct |
4 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 |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
4 ms |
492 KB |
Output is correct |
| 6 |
Correct |
4 ms |
492 KB |
Output is correct |
| 7 |
Correct |
237 ms |
7276 KB |
Output is correct |
| 8 |
Correct |
268 ms |
7276 KB |
Output is correct |
| 9 |
Correct |
246 ms |
7380 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 |
2 ms |
364 KB |
Output is correct |
| 5 |
Correct |
4 ms |
492 KB |
Output is correct |
| 6 |
Correct |
4 ms |
492 KB |
Output is correct |
| 7 |
Correct |
237 ms |
7276 KB |
Output is correct |
| 8 |
Correct |
268 ms |
7276 KB |
Output is correct |
| 9 |
Correct |
246 ms |
7380 KB |
Output is correct |
| 10 |
Correct |
2036 ms |
7404 KB |
Output is correct |
| 11 |
Correct |
2331 ms |
7396 KB |
Output is correct |
| 12 |
Correct |
2445 ms |
7292 KB |
Output is correct |
