| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 755487 |
2023-06-10T07:36:43 Z |
LeSonnn |
Toll (APIO13_toll) |
C++17 |
|
805 ms |
12308 KB |
#include <bits/stdc++.h>
#define task "a"
using namespace std;
typedef long long ll;
const int maxN = 1e5, maxM = 3e5, K = 20;
struct Edge
{
int x, y, w;
bool operator<(const Edge &o) const
{
return w < o.w;
}
} E[K + maxM];
int f[maxN + 1], rk[maxN + 1];
int F(int x)
{
return f[x] ? f[x] = F(f[x]) : x;
}
inline void reset(int n)
{
fill_n(f + 1, n, 0);
fill_n(rk + 1, n, 0);
}
inline void merge(int rx, int ry)
{
if (rx == ry) return;
if (rk[rx] < rk[ry]) swap(rx, ry);
f[ry] = rx;
rk[rx] += rk[rx] == rk[ry];
}
void kruskal(int n, int l, int r, int ans[])
{
int c = 0;
reset(n);
for(int i = l; i < r; i++)
{
int x = F(E[i].x), y = F(E[i].y);
if (x != y)
{
merge(x, y);
ans[c++] = i;
if (c == n - 1)
{
break;
}
}
}
}
int n, m, k, cnt, id[maxN + 1], p[maxN + 1], adj[K + 2], dep[K + 2], fa[K + 2];
ll sum[K + 2], ss[K + 2];
bool b[K + 2], used[2 * K];
struct List
{
int to, nxt;
bool b;
} L[2 * K + 1];
int ptr = 1;
inline void add(int x, int y, bool b)
{
L[ptr] = (List){y, adj[x], b};
adj[x] = ptr++;
}
void dfs(int u, int p)
{
ss[u] = sum[u];
for (int i = adj[u]; i; i = L[i].nxt)
{
int v = L[i].to;
if (v == p) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
b[v] = L[i].b;
dfs(v, u);
ss[u] += ss[v];
}
}
inline void update(int &x, int w, ll &ans)
{
if (!b[x]) return;
ans += w * ss[x];
b[x] = false;
}
ll cal(int s)
{
ptr = 1;
fill_n(adj + 1, cnt, 0);
reset(cnt);
for(int i = 0; i < k; i++)
{
if (s & (1 << i))
{
int x = E[i].x, y = E[i].y, rx = F(x), ry = F(y);
if (rx == ry) return 0;
add(x, y, true);
add(y, x, true);
merge(rx, ry);
}
}
for(int i = k ; i < cnt + k - 1; i++)
{
int x = E[i].x, y = E[i].y, rx = F(x), ry = F(y);
if (rx != ry)
{
add(x, y, false);
add(y, x, false);
merge(rx, ry);
used[i] = false;
}
else
{
used[i] = true;
}
}
dfs(1, 0);
ll ans = 0;
for(int i = k ; i < cnt + k - 1; i++)
{
if (used[i])
{
int x = E[i].x, y = E[i].y, w = E[i].w;
if (dep[y] < dep[x])
{
swap(x, y);
}
while (dep[y] != dep[x])
{
update(y, w, ans);
y = fa[y];
}
while (x != y)
{
update(x, w, ans);
update(y, w, ans);
x = fa[x];
y = fa[y];
}
}
}
return ans;
}
void progress()
{
cin >> n >> m >> k;
for (int i = k; i < k + m; i++)
{
cin >> E[i].x >> E[i].y >> E[i].w;
}
for (int i = 0; i < k; i++)
{
cin >> E[i].x >> E[i].y;
}
for (int i = 1; i <= n; i++)
{
cin >> p[i];
}
sort(E + k, E + k + m);
static int v[maxN - 1];
kruskal(n, 0, k + m, v);
reset(n);
for(int i = 0; i < n - 1; i++)
{
if (v[i] >= k)
{
merge(F(E[v[i]].x), F(E[v[i]].y));
}
}
for (int i = 1; i <= n; i++)
{
int j = F(i);
if (!id[j])
{
id[j] = ++cnt;
}
sum[id[i] = id[j]] += p[i];
}
for (int i = 0; i < k + m; i++)
{
E[i].x = id[E[i].x];
E[i].y = id[E[i].y];
}
kruskal(cnt, k, k + m, v);
for (int i = 0; i < cnt - 1; i++)
{
E[k + i] = E[v[i]];
}
ll ans(0);
for (int s = (1 << k) - 1; s >= (1 << (k - min(k, 2))); s--)
{
ans = max(ans, cal(s));
}
cout << ans;
}
// main
int main()
{
// Written by Shyn_
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
if (fopen(task ".inp", "r"))
{
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
ll nt = 1;
// cin >> nt;
for (; nt--;)
{
progress();
}
}
/** LeSonnn_ **/
/** LCG **/
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:228:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
228 | freopen(task ".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:229:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
229 | freopen(task ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
143 ms |
12160 KB |
Output is correct |
| 8 |
Correct |
152 ms |
12136 KB |
Output is correct |
| 9 |
Correct |
132 ms |
12104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
328 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
143 ms |
12160 KB |
Output is correct |
| 8 |
Correct |
152 ms |
12136 KB |
Output is correct |
| 9 |
Correct |
132 ms |
12104 KB |
Output is correct |
| 10 |
Correct |
580 ms |
12108 KB |
Output is correct |
| 11 |
Correct |
804 ms |
12308 KB |
Output is correct |
| 12 |
Correct |
805 ms |
12224 KB |
Output is correct |
