| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 626667 |
2022-08-11T15:39:56 Z |
messiuuuuu |
Toll (APIO13_toll) |
C++17 |
|
78 ms |
163840 KB |
///
#include<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 3e5 + 5;
const ll INF = 1e18 + 5;
int n, k, m;
struct TEdge
{
int u, v, w;
}es[MAXN], more[21];
int a[MAXN];
void Input()
{
cin >> n >> m >> k;
for (int i = 1; i <= m; i++)
{
cin >> es[i].u >> es[i].v >> es[i].w;
}
for (int i = 1; i <= k; i++)
{
cin >> more[i].u >> more[i].v;
}
for (int i = 1; i <= n; i++)
cin >> a[i];
}
int lab[MAXN], w[25][25], w1[25][25];
bool inmst[MAXN];
vector<pair<int, int>> Adj[25];
ll lab1[MAXN], sum[MAXN], res;
struct TRb
{
int u, v, labu, labv;
ll lab1u, lab1v;
}rb[25];
int szrb = 0;
void rollback(int sz)
{
while (szrb > sz)
{
auto top = rb[szrb];
lab[top.u] = top.labu;
lab[top.v] = top.labv;
lab1[top.u] = top.lab1u;
lab1[top.v] = top.lab1v;
szrb--;
}
}
int FindSet(int u)
{
return lab[u] < 0 ? u : FindSet(lab[u]);
}
bool Unite(int u, int v)
{
u = FindSet(u);
v = FindSet(v);
if (u == v)
return 0;
if (lab[u] > lab[v])
swap(u, v);
rb[++szrb] = {u, v, lab[u], lab[v], lab1[u], lab1[v]};
lab1[u] += lab1[v];
lab[u] += lab[v];
lab[v] = u;
return 1;
}
void DFS(int u, int par, ll val)
{
sum[u] = lab1[u];
for (auto v : Adj[u])
{
if (v.fi == par)
continue;
DFS(v.fi, u, val + v.se);
sum[u] += sum[v.fi];
}
res += val * sum[u];
}
void resetDsu()
{
memset(lab, -1, sizeof(lab));
for (int i = 1; i <= n; i++)
lab1[i] = a[i];
szrb = 0;
}
void Solve()
{
resetDsu();
for (int i = 1; i <= k; i++)
{
Unite(more[i].u, more[i].v);
}
sort(es + 1, es + 1 + m, [](const auto& i, const auto& j)
{
return i.w < j.w;
});
for (int i = 1; i <= m; i++)
{
if (Unite(es[i].u, es[i].v))
{
inmst[i] = 1;
}
}
resetDsu();
for (int i = 1; i <= m; i++)
{
if (inmst[i])
{
Unite(es[i].u, es[i].v);
}
}
vector<pair<int, int>> etplt;
for (int i = 1; i <= m; i++)
{
if (!inmst[i])
{
int u = FindSet(es[i].u), v = FindSet(es[i].v);
if (u > v)
swap(u, v);
if (!w[u][v])
{
w[u][v] = es[i].w;
etplt.pb({u, v});
}
}
}
sort(etplt.begin(), etplt.end(), [](const auto& i, const auto& j)
{
return w[i.fi][i.se] < w[j.fi][j.se];
});
ll ans = 0;
for (int mask = 1; mask < (1 << k); mask++)
{
int sz = szrb;
for (int i = 0; i < k; i++)
{
if (mask & (1 << i))
{
Unite(more[i + 1].u, more[i + 1].v);
}
}
vector<int> in, out;
for (int i = 0; i < etplt.size(); i++)
{
auto e = etplt[i];
if (Unite(e.fi, e.se))
{
in.pb(i);
} else
{
out.pb(i);
}
}
rollback(sz);
for (int i : in)
{
auto e = etplt[i];
Unite(e.fi, e.se);
}
for (int i : out)
{
auto e = etplt[i];
int u = FindSet(e.fi), v = FindSet(e.se);
if (u > v)
swap(u, v);
if (!w1[u][v])
w1[u][v] = w[u][v];
}
for (int i = 0; i < k; i++)
{
if (mask & (1 << i))
{
int r = FindSet(more[i + 1].u), s = FindSet(more[i + 1].v);
if (r > s)
swap(r, s);
Adj[r].pb({s, w1[r][s]});
Adj[s].pb({r, w1[r][s]});
}
}
res = 0;
DFS(FindSet(1), 0, 0);
ans = max(ans, res);
rollback(sz);
for (int i = 0; i < k; i++)
{
if (mask & (1 << i))
{
int r = FindSet(more[i + 1].u), s = FindSet(more[i + 1].v);
if (r > s)
swap(r, s);
Adj[r].clear();
Adj[s].clear();
}
}
for (int i : out)
{
auto e = etplt[i];
int u = FindSet(e.fi), v = FindSet(e.se);
if (u > v)
swap(u, v);
w1[u][v] = 0;
}
}
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(task".INP","r"))
{
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
Input();
Solve();
}
Compilation message
toll.cpp: In function 'void Solve()':
toll.cpp:159:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for (int i = 0; i < etplt.size(); i++)
| ~~^~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:230:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
230 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 3 |
Runtime error |
78 ms |
163840 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 3 |
Runtime error |
78 ms |
163840 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 3 |
Runtime error |
78 ms |
163840 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 3 |
Runtime error |
78 ms |
163840 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
