| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 889142 |
2023-12-19T03:09:04 Z |
damwuan |
Toll (APIO13_toll) |
C++14 |
|
979 ms |
44108 KB |
#include<bits/stdc++.h>
using namespace std;
#define task "test"
#define pb push_back
#define fi first
#define se second
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=6e5+69;
const ll inf=1e18;
const ll mod=1e9+7;
const ll base = 223;
int n, m, k;
int id[maxn], Cnt;
int dd[maxn];
struct Edge
{
int u, v, w;
bool operator < (const Edge& o) const
{
return w < o.w;
}
}e[maxn];
struct usd
{
int par[maxn];
void init(int x=n) {fill(par,par+1+x,-1);}
int Find(int u)
{
return par[u] < 0 ? u : par[u] = Find(par[u]);
}
bool Union(int u, int v)
{
if ((u = Find(u)) == (v = Find(v))) return false;
if (par[u] > par[v]) swap(u,v);
par[u] += par[v];
par[v] = u;
return true;
}
}dsu;
vector<pii> adj[maxn];
vector<int> used, tocheck;
int ans, res,sum[maxn], dep[maxn], up[maxn], a[maxn] , sm[maxn];
bool spe[maxn];
void dfs(int u,int pre)
{
dep[u]=dep[pre]+1;
up[u] = pre;
sm[u]=sum[u];
for (auto x: adj[u])
{
int v=x.fi;
int w=x.se;
if (v==pre) continue;
dfs(v,u);
sm[u]+=sm[v];
if (w <= -inf) spe[v]=1;
}
}
void lca(int u,int v,int w)
{
if (dep[u] < dep[v]) swap(u,v);
while (dep[u] > dep[v])
{
if (spe[u])
{
res+=sm[u]*w;
spe[u]=0;
}
u=up[u];
}
while (u!=v)
{
if (spe[u])
{
res+=sm[u]*w;
spe[u]=0;
}
if (spe[v])
{
res+=sm[v]*w;
spe[v]=0;
}
u=up[u];
v=up[v];
}
}
int cal(int mask)
{
res=0;
tocheck.clear();
for (int i = 1; i <= Cnt;i++)
{
adj[i].clear();
spe[i]=0;
dep[i]=0;
}
dsu.init(Cnt);
for (int i=1;i<=k;i++)
{
if ((mask>>(i-1))&1)
{
if (dsu.Union(e[i].u,e[i].v))
{
adj[e[i].u].pb({e[i].v, -inf});
adj[e[i].v].pb({e[i].u, -inf});
}
else return 0;
}
}
for (int i: used)
{
int u=e[i].u;
int v=e[i].v;
int w=e[i].w;
if (dsu.Union(u, v))
{
adj[u].pb({v,w});
adj[v].pb({u,w});
}
else tocheck.pb(i);
}
dfs(1,1);
for (int i: tocheck) lca(e[i].u, e[i].v, e[i].w);
return res;
}
void sol()
{
cin >> n >> m >> k;
for (int i = 1;i <= m ;i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
}
for (int i = m+1;i <= m+k;i++)
{
cin >> e[i].u >> e[i].v;
e[i].w=-inf;
}
for (int i = 1;i <= n; i++)
{
cin >> a[i];
}
sort(e + 1, e + 1 + m + k);
dsu.init();
for (int i = 1; i <= k ; i++)
{
dsu.Union(e[i].u, e[i].v);
}
for (int i = k+1; i <= m+k; i++)
{
if (dsu.Union(e[i].u,e[i].v))
{
used.pb(i);
}
}
dsu.init();
for (int i: used) dsu.Union(e[i].u, e[i].v);
for (int i = 1;i <= n ;i++)
{
int x = dsu.Find(i);
if (!dd[x]) dd[x]=++Cnt;
id[i] = dd[x];
sum[dd[x]]+=a[i];
}
for (int i = 1;i <= m+k; i++)
{
e[i].u = id[e[i].u];
e[i].v = id[e[i].v];
}
used.clear();
dsu.init(Cnt);
// for (int i = 1 ;i <= k; i++)
// {
// Union(e[i].u,e[i].v);
// }
for (int i = k + 1 ;i <= k+m; i++)
{
if(dsu.Union(e[i].u, e[i].v))
{
used.pb(i);
}
}
for (int mask = 1; mask < (1<<k) ; mask++)
{
ans= max(ans,cal(mask));
}
cout << ans;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
int t=1;//cin >> t;
while (t--)
{
sol();
}
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/
Compilation message
toll.cpp: In function 'int32_t main()':
toll.cpp:203:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
203 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:204:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
204 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 2 |
Correct |
5 ms |
29020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 2 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 3 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 4 |
Correct |
6 ms |
29208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 2 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 3 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 4 |
Correct |
6 ms |
29208 KB |
Output is correct |
| 5 |
Correct |
7 ms |
29276 KB |
Output is correct |
| 6 |
Correct |
7 ms |
29316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 2 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 3 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 4 |
Correct |
6 ms |
29208 KB |
Output is correct |
| 5 |
Correct |
7 ms |
29276 KB |
Output is correct |
| 6 |
Correct |
7 ms |
29316 KB |
Output is correct |
| 7 |
Correct |
113 ms |
43880 KB |
Output is correct |
| 8 |
Correct |
118 ms |
43920 KB |
Output is correct |
| 9 |
Correct |
114 ms |
43876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 2 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 3 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 4 |
Correct |
6 ms |
29208 KB |
Output is correct |
| 5 |
Correct |
7 ms |
29276 KB |
Output is correct |
| 6 |
Correct |
7 ms |
29316 KB |
Output is correct |
| 7 |
Correct |
113 ms |
43880 KB |
Output is correct |
| 8 |
Correct |
118 ms |
43920 KB |
Output is correct |
| 9 |
Correct |
114 ms |
43876 KB |
Output is correct |
| 10 |
Correct |
758 ms |
44108 KB |
Output is correct |
| 11 |
Correct |
973 ms |
43984 KB |
Output is correct |
| 12 |
Correct |
979 ms |
43984 KB |
Output is correct |
