| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15937 |
2015-08-02T08:24:27 Z |
myungwoo |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
7592 KB |
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXM 300005
#define pb push_back
#define sz(v) ((int)(v).size())
typedef long long lld;
int N, M, K, C;
int A[MAXN];
int par[MAXN], num[MAXN], H[23], tpar[23];
int up[23], is_g[23];
lld subtree_sz[23], sz[23], ans;
vector <int> tcon[23], tconv[23], tcont[23];
struct EDGE{
int a, b, c;
bool in_mst, is_critical;
} E[MAXM], F[21];
int cp(int n){ return par[n] == n ? n : (par[n] = cp(par[n])); }
void make_tree(int n, int from)
{
subtree_sz[n] = sz[n];
for (int i=sz(tcon[n]);i--;){
int t = tcon[n][i], v = tconv[n][i], p = tcont[n][i];
if (t == from) continue;
H[t] = H[n] + 1; up[t] = v; tpar[t] = n; is_g[t] = p;
make_tree(t, n);
subtree_sz[n] += subtree_sz[t];
}
}
inline void set_edges()
{
for (int i=1;i<=C;i++) tcon[i].clear(), tconv[i].clear(), tcont[i].clear();
for (int i=2;i<=C;i++){
int a = tpar[i], b = i, c = up[i], t = is_g[i];
if (!a) continue;
tcon[a].pb(b); tconv[a].pb(c); tcont[a].pb(t);
tcon[b].pb(a); tconv[b].pb(c); tcont[b].pb(t);
}
}
void dfs(int n, int cnt)
{
if (n > K){
if (!cnt) return;
lld val = 0;
for (int i=2;i<=C;i++) if (is_g[i]){
val += up[i] * subtree_sz[i];
}
ans = max(ans, val);
return;
}
dfs(n+1, cnt);
int a = F[n].a, b = F[n].b;
if (H[a] < H[b]) swap(a, b);
vector <int> arr;
while (H[a] > H[b]) arr.pb(a), a = tpar[a];
while (a != b) arr.pb(a), arr.pb(b), a = tpar[a], b = tpar[b];
int mx = 0, target;
for (int t: arr) if (!is_g[t]){
if (mx < up[t])
mx = up[t], target = t;
}
if (!mx) return;
vector <int> _tpar(tpar, tpar+C+1), _is_g(is_g, is_g+C+1), _up(up, up+C+1);
for (int t: arr) if (is_g[t]) up[t] = min(up[t], mx);
tpar[target] = 0;
set_edges();
a = F[n].a, b = F[n].b;
tcon[a].pb(b); tconv[a].pb(mx); tcont[a].pb(1);
tcon[b].pb(a); tconv[b].pb(mx); tcont[b].pb(1);
make_tree(1, 0);
dfs(n+1, cnt+1);
for (int i=1;i<=C;i++)
tpar[i] = _tpar[i], is_g[i] = _is_g[i], up[i] = _up[i];
set_edges();
make_tree(1, 0);
}
int main()
{
scanf("%d%d%d", &N, &M, &K);
for (int i=1;i<=M;i++) scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].c);
for (int i=1;i<=K;i++) scanf("%d%d", &F[i].a, &F[i].b);
for (int i=1;i<=N;i++) scanf("%d", A+i);
sort(E+1, E+M+1, [](const EDGE &a, const EDGE &b){
return a.c < b.c;
});
for (int i=1;i<=N;i++) par[i] = i;
for (int i=1;i<=M;i++){
int a = cp(E[i].a), b = cp(E[i].b);
if (a == b) continue;
par[b] = a;
E[i].in_mst = 1;
}
for (int i=1;i<=N;i++) par[i] = i;
for (int i=1;i<=K;i++){
int a = cp(F[i].a), b = cp(F[i].b);
par[b] = a;
}
for (int i=1;i<=M;i++) if (E[i].in_mst){
int a = cp(E[i].a), b = cp(E[i].b);
if (a == b) E[i].is_critical = 1;
par[b] = a;
}
for (int i=1;i<=N;i++) par[i] = i;
for (int i=1;i<=M;i++) if (E[i].in_mst && !E[i].is_critical){
int a = cp(E[i].a), b = cp(E[i].b);
if (a > b) swap(a, b);
par[b] = a;
}
for (int i=1;i<=N;i++) if (cp(i) == i){
num[i] = ++C;
}
for (int i=1;i<=N;i++) sz[num[cp(i)]] += A[i];
vector <EDGE> critical;
for (int i=1;i<=M;i++) if (E[i].is_critical){
int a = num[cp(E[i].a)] , b = num[cp(E[i].b)];
critical.pb({a, b, E[i].c});
}
for (int i=1;i<=K;i++) F[i].a = num[cp(F[i].a)], F[i].b = num[cp(F[i].b)];
for (auto &e: critical){
tcon[e.a].pb(e.b); tconv[e.a].pb(e.c); tcont[e.a].pb(0);
tcon[e.b].pb(e.a); tconv[e.b].pb(e.c); tcont[e.b].pb(0);
}
make_tree(1, 0);
dfs(1, 0);
printf("%lld\n", ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
7592 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
7592 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
7592 KB |
Output is correct |
| 2 |
Correct |
0 ms |
7592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
259 ms |
7592 KB |
Output is correct |
| 2 |
Correct |
227 ms |
7592 KB |
Output is correct |
| 3 |
Correct |
242 ms |
7592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2186 ms |
7592 KB |
Output is correct |
| 2 |
Execution timed out |
2500 ms |
7592 KB |
Program timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
