| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 744958 |
2023-05-19T09:00:58 Z |
victor_gao |
Toll (APIO13_toll) |
C++17 |
|
3 ms |
5076 KB |
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,k,m,cost[30],fa[N],sz[N],dep[N],isnew[N];
int dp1[(1<<20)+5],val[30][30],ans=0;
pii dp[N];
set<pii>g[N];
vector<pair<int,pii> >edge,out;
struct DSU{
int boss[N],sz[N];
void init(int n){
for (int i=1;i<=n;i++){
boss[i]=i;
sz[i]=1;
}
}
int find(int x){
if (boss[x]==x) return x;
return boss[x]=find(boss[x]);
}
void merge(int a,int b){
int ra=find(a),rb=find(b);
if (ra==rb) return;
if (sz[ra]<sz[rb]) swap(ra,rb);
sz[ra]+=sz[rb];
boss[rb]=ra;
}
}d;
void dfs(int p,int lp,int c){
dp[p]=max(dp[lp],pii(c,p));
fa[p]=lp;
for (auto i:g[p]){
if (i.x!=lp)
dfs(i.x,p,i.y);
}
}
void dfs1(int p,int lp,int c){
fa[p]=lp; dep[p]=dep[lp]+1;
if (c>=0) isnew[p]=c;
for (auto [i,id]:g[p]){
if (i!=lp){
dfs1(i,p,-id);
sz[p]+=sz[i];
}
}
}
void jump(int a,int b,int num,int c){
while (a!=b){
if (dep[a]<dep[b]) swap(a,b);
if (isnew[a]>=0){
val[isnew[a]][num]=sz[a]*c;
}
a=fa[a];
}
}
signed main(){
fast
cin>>n>>m>>k;
for (int i=1;i<=m;i++){
int a,b,c; cin>>a>>b>>c;
edge.push_back({c,{a,b}});
}
sort(edge.begin(),edge.end());
d.init(n);
for (auto [c,tmp]:edge){
auto [a,b]=tmp;
if (d.find(a)!=d.find(b)){
d.merge(a,b);
g[a].insert({b,c});
g[b].insert({a,c});
}
}
for (int i=0;i<k;i++){
int a,b; cin>>a>>b;
dfs(a,0,0);
if (dp[b].x<0) continue;
else {
int p=dp[b].y;
g[p].erase(pii(fa[p],dp[b].x));
g[fa[p]].erase(pii(p,dp[b].x));
g[a].insert({b,-i});
g[b].insert({a,-i});
cost[i]=dp[b].x;
out.push_back({dp[b].x,{p,fa[p]}});
}
}
for (int i=1;i<=n;i++){
cin>>sz[i];
isnew[i]=-1;
}
dfs1(1,0,-1);
for (int i=0;i<=k;i++)
for (int j=0;j<=k;j++)
val[i][j]=-1e9;
k=out.size();
for (int i=0;i<k;i++)
jump(out[i].y.x,out[i].y.y,i,out[i].x);
/*
for (int i=0;i<k;i++){
for (int j=0;j<k;j++)
cout<<val[i][j]<<" ";
cout<<'\n';
}
*/
for (int i=0;i<k;i++){
for (int j=0;j<(1LL<<k);j++){
for (int l=0;l<k;l++){
if (j&(1LL<<l))
dp1[j]=max(dp1[j],dp1[j^(1LL<<l)]+val[i][l]);
}
}
}
cout<<dp1[(1LL<<k)-1]<<'\n';
}
/*
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
