| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171010 |
2019-12-27T04:03:09 Z |
PeppaPig |
Toll (APIO13_toll) |
C++14 |
|
3 ms |
888 KB |
#include <bits/stdc++.h>
#define long long long
#define iii tuple<int, int, int>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e5+5;
int dsu[N], dsu_size = N;
void init() { iota(dsu, dsu + dsu_size, 0); }
int find(int x) { return dsu[x] = x == dsu[x] ? x : find(dsu[x]); }
int n, m, k;
long ans;
vector<iii> E, sure, cmp;
vector<pii> toll;
vector<int> g[25];
int cid[N], csz[N], sz[N];
int par[25], dep[25], weight[25], subsz[25], chk[25];
void dfs(int u, int p) {
par[u] = p, dep[u] = dep[p] + 1;
for(int v : g[u]) if(v != p) {
dfs(v, u);
subsz[u] += subsz[v];
}
}
int main() {
scanf("%d %d %d", &n, &m, &k);
for(int i = 1, a, b, c; i <= m; i++) {
scanf("%d %d %d", &a, &b, &c);
E.emplace_back(c, a, b);
}
sort(E.begin(), E.end());
init();
vector<iii> mst_edge;
for(iii e : E) {
int a, b, c; tie(c, a, b) = e;
if(find(a) != find(b)) {
dsu[find(a)] = find(b);
mst_edge.emplace_back(e);
}
}
swap(E, mst_edge);
init();
for(int i = 1, a, b; i <= k; i++) {
scanf("%d %d", &a, &b);
toll.emplace_back(a, b);
dsu[find(a)] = find(b);
}
for(int i = 1; i <= n; i++) scanf("%d", sz + i);
for(iii e : E) {
int a, b, c; tie(c, a, b) = e;
if(find(a) != find(b)) {
dsu[find(a)] = find(b);
sure.emplace_back(e);
} else cmp.emplace_back(e);
}
init();
for(iii e : sure) {
int a, b, c; tie(c, a, b) = e;
dsu[find(a)] = find(b);
}
int ptr = 0;
for(int i = 1; i <= n; i++) if(find(i) == i)
cid[i] = ++ptr;
dsu_size = ptr;
for(int i = 1; i <= n; i++) if(find(i) != i)
cid[i] = cid[find(i)];
for(int i = 1; i <= n; i++)
csz[cid[i]] += sz[i];
for(int bit = 0; bit < (1 << k); bit++) {
init();
memset(chk, 0, sizeof chk);
for(int i = 1; i <= ptr; i++) {
g[i].clear();
subsz[i] = csz[i];
}
bool valid = true;
for(int i = 0; i < k; i++) if(bit >> i & 1) {
int a = toll[i].x, b = toll[i].y;
if(find(cid[a]) == find(cid[b])) {
valid = false;
break;
} else {
g[cid[a]].emplace_back(cid[b]);
g[cid[b]].emplace_back(cid[a]);
dsu[find(cid[a])] = find(cid[b]);
}
}
if(!valid) continue;
for(int i = 0; i < cmp.size(); i++) {
int a, b, c; tie(c, a, b) = cmp[i];
if(find(cid[a]) != find(cid[b])) {
g[cid[a]].emplace_back(cid[b]);
g[cid[b]].emplace_back(cid[a]);
dsu[find(cid[a])] = find(cid[b]);
chk[i] = true;
}
}
dfs(cid[1], 0);
for(int i = 0; i < cmp.size(); i++) if(chk[i]) {
int a, b, c; tie(c, a, b) = cmp[i];
if(par[cid[b]] == cid[a]) swap(a, b);
weight[cid[a]] = 0;
}
for(int i = 0; i < k; i++) if(bit >> i & 1) {
int a, b; tie(a, b) = toll[i];
if(par[cid[b]] == cid[a]) swap(a, b);
weight[cid[a]] = 1e9;
}
for(int i = 0; i < cmp.size(); i++) if(!chk[i]) {
int a = get<1>(cmp[i]), b = get<2>(cmp[i]), c = get<0>(cmp[i]);
a = cid[a], b = cid[b];
if(dep[a] < dep[b]) swap(a, b);
while(dep[a] > dep[b]) {
weight[a] = min(weight[a], c);
a = par[a];
}
while(a != b) {
weight[a] = min(weight[a], c);
weight[b] = min(weight[b], c);
a = par[a], b = par[b];
}
}
long ret = 0;
for(int i = 1; i <= ptr; i++) ret += 1ll * weight[i] * subsz[i];
ans = max(ans, ret);
}
printf("%lld\n", ans);
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:105:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < cmp.size(); i++) {
~~^~~~~~~~~~~~
toll.cpp:116:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < cmp.size(); i++) if(chk[i]) {
~~^~~~~~~~~~~~
toll.cpp:127:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < cmp.size(); i++) if(!chk[i]) {
~~^~~~~~~~~~~~
toll.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
toll.cpp:61:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= n; i++) scanf("%d", sz + i);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
888 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
888 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
888 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
888 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
888 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
760 KB |
Output isn't correct |
