| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 248463 |
2020-07-12T13:32:40 Z |
receed |
Toll (APIO13_toll) |
C++14 |
|
2005 ms |
30548 KB |
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int N = 100001, K = 21, INF = 1e7;
pair<int, int> cg[K][K];
int cgs[K];
vector<int> re[K];
int p[N], r[N], np[N], par[K], uw[K], dw[K], cnt[N], h[K];
ll val[K], sum[K];
int getp(int v) {
if (p[v] != v)
p[v] = getp(p[v]);
return p[v];
}
int merge(int u, int v) {
u = getp(u);
v = getp(v);
if (u == v)
return 0;
if (r[u] > r[v])
p[v] = u;
else {
p[u] = v;
if (r[u] == r[v])
r[v]++;
}
return 1;
}
void dfs(int v, int p) {
par[v] = p;
sum[v] = val[v];
rep(i, cgs[v]) {
auto pp = cg[v][i];
if (pp.first == p)
continue;
dw[pp.first] = (pp.second == -1 ? 1 : 0);
h[pp.first] = h[v] + 1;
dfs(pp.first, v);
sum[v] += sum[pp.first];
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> e(m, vector<int>(3)), ne(k, vector<int>(3, -1)), ce, de;
rep(i, m) {
cin >> e[i][1] >> e[i][2] >> e[i][0];
e[i][1]--; e[i][2]--;
}
sort(all(e));
rep(i, n)
p[i] = i;
rep(i, k) {
cin >> ne[i][1] >> ne[i][2];
ne[i][1]--;
ne[i][2]--;
}
for (auto &pp : e)
if (merge(pp[1], pp[2]))
ne.push_back(pp);
rep(i, n) {
p[i] = i;
r[i] = 0;
}
for (auto &pp : ne) {
if (merge(pp[1], pp[2]) && pp[0] > -1)
ce.push_back(pp);
else if (pp[0] > -1)
de.push_back(pp);
}
rep(i, n) {
p[i] = i;
r[i] = 0;
}
for (auto &pp : ce)
merge(pp[1], pp[2]);
vector<int> li;
rep(i, n)
li.push_back(getp(i));
sort(all(li));
li.resize(unique(all(li)) - li.begin());
rep(i, n) {
np[i] = lower_bound(all(li), p[i]) - li.begin();
cin >> cnt[i];
val[np[i]] += cnt[i];
}
rep(i, ne.size()) {
ne[i][1] = np[ne[i][1]];
ne[i][2] = np[ne[i][2]];
}
rep(i, de.size()) {
de[i][1] = np[de[i][1]];
de[i][2] = np[de[i][2]];
}
int nn = li.size(), rt = np[p[0]];
ll ans = 0, ca;
rep(i, nn)
re[i] = vector<int>(3);
rep(i, 1 << k) {
int f = 0;
rep(j, nn) {
p[j] = j;
r[j] = 0;
cgs[j] = 0;
}
rep(j, k)
if ((i & (1 << j))) {
int v1 = ne[j][1], v2 = ne[j][2];
if (!merge(v1, v2)) {
f = 1;
break;
}
cg[v1][cgs[v1]++] = {v2, -1};
cg[v2][cgs[v2]++] = {v1, -1};
}
if (f)
continue;
int rs = 0;
for (auto &pp : de) {
if (merge(pp[1], pp[2])) {
cg[pp[1]][cgs[pp[1]]++] = {pp[2], pp[0]};
cg[pp[2]][cgs[pp[2]]++] = {pp[1], pp[0]};
}
else
re[rs++] = pp;
}
dfs(rt, -1);
for (int i = rs - 1; i >= 0; i--) {
auto pp = re[i];
int v1 = pp[1], v2 = pp[2];
while (h[v2] > h[v1]) {
uw[v2] = pp[0];
v2 = par[v2];
}
while (h[v1] > h[v2]) {
uw[v1] = pp[0];
v1 = par[v1];
}
while (v1 != v2) {
uw[v1] = pp[0];
v1 = par[v1];
uw[v2] = pp[0];
v2 = par[v2];
}
}
ca = 0;
rep(j, nn)
ca += uw[j] * dw[j] * sum[j];
ans = max(ans, ca);
}
cout << ans;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i, n) for (int i = 0; i < (n); i++)
^
toll.cpp:116:5: note: in expansion of macro 'rep'
rep(i, ne.size()) {
^~~
toll.cpp:19:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i, n) for (int i = 0; i < (n); i++)
^
toll.cpp:120:5: note: in expansion of macro 'rep'
rep(i, de.size()) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
768 KB |
Output is correct |
| 6 |
Correct |
3 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
768 KB |
Output is correct |
| 6 |
Correct |
3 ms |
768 KB |
Output is correct |
| 7 |
Correct |
306 ms |
30256 KB |
Output is correct |
| 8 |
Correct |
320 ms |
30288 KB |
Output is correct |
| 9 |
Correct |
333 ms |
30244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
768 KB |
Output is correct |
| 6 |
Correct |
3 ms |
768 KB |
Output is correct |
| 7 |
Correct |
306 ms |
30256 KB |
Output is correct |
| 8 |
Correct |
320 ms |
30288 KB |
Output is correct |
| 9 |
Correct |
333 ms |
30244 KB |
Output is correct |
| 10 |
Correct |
1524 ms |
30420 KB |
Output is correct |
| 11 |
Correct |
1969 ms |
30548 KB |
Output is correct |
| 12 |
Correct |
2005 ms |
30492 KB |
Output is correct |
