| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 626980 |
2022-08-12T04:01:45 Z |
messiuuuuu |
Toll (APIO13_toll) |
C++14 |
|
3 ms |
1492 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;
const int MAXK = 25;
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[MAXK][MAXK], w1[MAXK][MAXK];
bool inmst[MAXN];
vector<int> Adj[MAXK];
ll lab1[MAXN], sum[25], res;
int labmau[25], tplt;
struct TRb
{
int u, v, labu, labv;
ll lab1u, lab1v;
}rb[MAXN];
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)
{
for (int v : Adj[u])
{
if (v == par)
continue;
int ts = 1e9, lu = FindSet(u);
for (int j = 1; j < v; j++)
{
if (w1[j][v] && FindSet(j) == lu)
{
ts = min(ts, w1[j][v]);
}
}
for (int j = v + 1; j <= tplt; j++)
{
if (w1[v][j] && FindSet(j) == lu)
{
ts = min(ts, w1[v][j]);
}
}
int sz = szrb;
Unite(u, v);
DFS(v, u, ts);
rollback(sz);
sum[u] += sum[v];
}
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 resetNen()
{
for (int i = 1; i <= tplt; i++)
{
lab[i] = -1;
lab1[i] = labmau[i];
}
szrb = 0;
}
int ds[MAXN];
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);
}
}
tplt = 0;
for (int i = 1; i <= n; i++)
{
int u = FindSet(i);
if (!ds[u])
{
ds[u] = ++tplt;
}
ds[i] = ds[u];
}
for (int i = 1; i <= n; i++)
{
assert(ds[i] <= i);
if (lab[i] < 0)
{
labmau[ds[i]] = lab1[i];
}
}
assert(tplt < MAXK);
resetNen();
//cout << tplt << '\n';
vector<pair<int, int>> etplt;
for (int i = 1; i <= m; i++)
{
if (!inmst[i])
{
int u = FindSet(ds[es[i].u]), v = FindSet(ds[es[i].v]);
if (u > v)
swap(u, v);
assert(u < MAXK && v < MAXK);
if (!w[u][v])
{
w[u][v] = es[i].w;
etplt.pb({u, v});
//cout << u << ' ' << v << ' ' << w[u][v] << '\n';
}
}
}
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++)
{
resetNen();
for (int i = 0; i < k; i++)
{
if (mask & (1 << i))
{
Unite(ds[more[i + 1].u], ds[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);
}
}
resetNen();
//cout << in.size() << ' ' << out.size() << '\n';
//cout << lab1[3] << '\n';
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);
assert(u < MAXK && v < MAXK);
if (!w1[u][v])
w1[u][v] = w[u][v];
}
for (int i = 0; i < k; i++)
{
if (mask & (1 << i))
{
int r = FindSet(ds[more[i + 1].u]), s = FindSet(ds[more[i + 1].v]);
assert(r < MAXK && s < MAXK);
Adj[r].pb(s);
Adj[s].pb(r);
}
}
for (int i = 1; i <= tplt; i++)
{
sum[i] = 0;
if (lab[i] < 0)
sum[i] = lab1[i];
}
res = 0;
DFS(FindSet(ds[1]), 0, 0);
ans = max(ans, res);
//cout << mask << ' ' << res << '\n';
for (int i = 1; i <= tplt; i++)
{
Adj[i].clear();
for (int j = i + 1; j <= tplt; j++)
{
w1[i][j] = 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:218: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]
218 | for (int i = 0; i < etplt.size(); i++)
| ~~^~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:288:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
288 | 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 |
Incorrect |
3 ms |
1492 KB |
Output isn't correct |
| 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 |
Incorrect |
3 ms |
1492 KB |
Output isn't correct |
| 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 |
Incorrect |
3 ms |
1492 KB |
Output isn't correct |
| 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 |
Incorrect |
3 ms |
1492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
