| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 248454 |
2020-07-12T13:15:54 Z |
receed |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
35512 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, L = 5, INF = 1e7;
vector<pair<int, int>> cg[K], dg[K];
vector<int> td[K], ta[K];
int up[L][K], tin[K], tout[K], ct;
multiset<int> ms[K];
int p[N], r[N], np[N], par[K], uw[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;
}
int isp(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
void dfs(int v, int p) {
up[0][v] = p;
tin[v] = ct++;
sum[v] = val[v];
for (auto &pp : cg[v]) {
if (pp.first == p)
continue;
h[pp.first] = h[v] + 1;
uw[pp.first] = (pp.second == -1 ? INF : 0);
dfs(pp.first, v);
sum[v] += sum[pp.first];
}
tout[v] = ct;
}
void dfs2(int v, int p) {
for (int i : ta[v])
ms[v].insert(i);
for (auto &pp : cg[v]) {
if (pp.first == p)
continue;
dfs2(pp.first, v);
// if (ms[v].size() < ms[pp.first].size())
// swap(ms[v], ms[pp.first]);
for (int i : ms[pp.first])
ms[v].insert(i);
}
for (int i : td[v]) {
ms[v].erase(ms[v].find(i));
ms[v].erase(ms[v].find(i));
}
if (uw[v])
uw[v] = *ms[v].begin();
}
int lca(int u, int v) {
if (isp(u, v))
return u;
for (int i = L - 1; i >= 0; i--)
if (!isp(up[i][u], v))
u = up[i][u];
return up[0][u];
}
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, 1 << k) {
int f = 0;
rep(j, nn) {
p[j] = j;
r[j] = 0;
cg[j].clear();
ms[j].clear();
ta[j].clear();
td[j].clear();
}
rep(j, k)
if ((i & (1 << j))) {
if (!merge(ne[j][1], ne[j][2])) {
f = 1;
break;
}
cg[ne[j][1]].push_back({ne[j][2], -1});
cg[ne[j][2]].push_back({ne[j][1], -1});
}
if (f)
continue;
vector<vector<int>> re;
for (auto &pp : de) {
if (merge(pp[1], pp[2])) {
cg[pp[1]].push_back({pp[2], pp[0]});
cg[pp[2]].push_back({pp[1], pp[0]});
}
else {
re.push_back(pp);
// dg[pp[1]].push_back({pp[2], pp[0]});
// dg[pp[2]].push_back({pp[1], pp[0]});
}
}
ct = 0;
dfs(rt, rt);
rep(i, L - 1)
rep(j, nn)
up[i + 1][j] = up[i][up[i][j]];
/*for (auto &pp : re) {
int v1 = pp[1], v2 = pp[2];
while (h[v2] > h[v1]) {
uw[v2] = min(uw[v2], pp[0]);
v2 = par[v2];
}
while (h[v1] > h[v2]) {
uw[v1] = min(uw[v1], pp[0]);
v1 = par[v1];
}
while (v1 != v2) {
uw[v1] = min(uw[v1], pp[0]);
v1 = par[v1];
uw[v2] = min(uw[v2], pp[0]);
v2 = par[v2];
}
}*/
for (auto &pp : re) {
int l = lca(pp[1], pp[2]);
ta[pp[1]].push_back(pp[0]);
ta[pp[2]].push_back(pp[0]);
td[l].push_back(pp[0]);
// cout << l << "?\n";
}
dfs2(rt, rt);
ca = 0;
rep(j, nn)
ca += uw[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:151: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:155: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 |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 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 |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
896 KB |
Output is correct |
| 6 |
Correct |
5 ms |
896 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 |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
896 KB |
Output is correct |
| 6 |
Correct |
5 ms |
896 KB |
Output is correct |
| 7 |
Correct |
393 ms |
35416 KB |
Output is correct |
| 8 |
Correct |
483 ms |
35492 KB |
Output is correct |
| 9 |
Correct |
439 ms |
35412 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 |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
6 ms |
896 KB |
Output is correct |
| 6 |
Correct |
5 ms |
896 KB |
Output is correct |
| 7 |
Correct |
393 ms |
35416 KB |
Output is correct |
| 8 |
Correct |
483 ms |
35492 KB |
Output is correct |
| 9 |
Correct |
439 ms |
35412 KB |
Output is correct |
| 10 |
Execution timed out |
2568 ms |
35512 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
