| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1108666 |
2024-11-04T18:32:47 Z |
vivkostov |
Toll (APIO13_toll) |
C++14 |
|
3 ms |
19024 KB |
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const long long int inf=2000000000000000001;
struct cell
{
long long int to,st;
};
struct poin
{
long long int a,b,c;
};
bool cmp(poin a1,poin a2)
{
return a1.c<a2.c;
}
long long int n,m,k,br[100005],st[100005],l[100],r[100],used[100005],lead[100005],sz[100005],num[100005],use[100005],basic_lead[100005],numb,group[200005];
long long int otg[2000005],par[200005],dpmi[200005],dpbr[200005];
cell mi[100005];
poin f[300005];
vector<cell>v[100005];
stack<pair<int,int>>s;
void prec()
{
for(int i=1;i<=n;i++)
{
lead[i]=i;
sz[i]=1;
num[i]=br[i];
}
for(int i=1;i<=n;i++)
{
mi[i].st=inf;
}
}
int get_lead(int beg)
{
if(beg==lead[beg])return beg;
return lead[beg]=get_lead(lead[beg]);
}
int get_lead2(int beg)
{
if(beg==lead[beg])return beg;
return get_lead(lead[beg]);
}
void add1(int a,int b)
{
a=get_lead(a);
b=get_lead(b);
if(a==b||(used[a]&&used[b]))return;
if(sz[a]<sz[b])swap(a,b);
if(used[b])used[a]=1;
lead[b]=a;
sz[a]+=sz[b];
num[a]+=num[b];
}
void add2(int a,int b)
{
a=get_lead2(a);
b=get_lead2(b);
if(sz[a]<sz[b])swap(a,b);
lead[b]=a;
sz[a]+=sz[b];
num[a]+=num[b];
pair<int,int>p;
p.first=a;
p.second=b;
s.push(p);
}
void rem()
{
int a=s.top().first,b=s.top().second;
sz[a]-=sz[b];
num[a]-=num[b];
lead[b]=b;
s.pop();
}
void get_min_vertex()
{
int a1,a2;
for(int i=1;i<=m;i++)
{
a1=get_lead(f[i].a);
a2=get_lead(f[i].b);
if(a1!=a2)
{
if(mi[a1].st>f[i].c)
{
mi[a1].st=f[i].c;
mi[a1].to=a2;
}
if(mi[a2].st>f[i].c)
{
mi[a2].st=f[i].c;
mi[a2].to=a1;
}
}
}
}
void check()
{
for(int i=1;i<=n;i++)
{
cout<<i<<" "<<lead[i]<<" "<<sz[i]<<" "<<num[i]<<endl;
}
cout<<endl;
for(int i=1;i<=n;i++)
{
cout<<mi[i].st<<" "<<mi[i].to<<" "<<i<<endl;
}
for(int i=1;i<=numb;i++)
{
cout<<basic_lead[i]<<" "<<par[basic_lead[i]]<<endl;
}
}
void get_basic()
{
memset(used,0,sizeof(used));
int l;
for(int i=1;i<=n;i++)
{
l=get_lead(i);
if(!used[l])
{
used[l]=1;
numb++;
basic_lead[numb]=l;
}
}
}
void dfs(int beg,int p)
{
int w;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i].to;
if(w!=p)
{
par[w]=v[beg][i].st;
dfs(w,beg);
}
}
}
void Clear()
{
int w;
for(int i=1;i<=numb;i++)
{
w=basic_lead[i];
v[w].clear();
dpbr[w]=0;
dpmi[w]=inf;
}
}
void get_par()
{
int w,brx=0;
cell h;
for(int i=1;i<=numb;i++)
{
w=basic_lead[i];
if(get_lead2(w)!=get_lead2(mi[w].to))
{
add2(w,mi[w].to);
h.to=w;
h.st=mi[w].st;
v[w].push_back(mi[w]);
v[mi[w].to].push_back(h);
brx++;
}
}
dfs(get_lead(1),0);
for(int i=1;i<=brx;i++)rem();
Clear();
/*for(int i=1;i<=numb;i++)
{
w=basic_lead[i];
cout<<w<<endl;
for(int j=0;j<v[w].size();j++)
{
cout<<v[w][j].to<<" "<<v[w][j].st<<endl;
}
cout<<endl;
}
*/
}
long long int dfs1(int beg,int p)
{
int w;
long long int sum=0;
dpmi[beg]=par[beg];
dpbr[beg]=num[beg];
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i].to;
if(w!=p)
{
sum+=dfs1(w,beg);
if(v[beg][i].st==-1)
{
sum+=dpmi[w]*dpbr[w];
}
dpmi[beg]=min(dpmi[beg],dpmi[w]);
dpbr[beg]+=dpbr[w];
}
}
//cout<<beg<<" "<<dpmi[beg]<<" "<<dpbr[beg]<<" "<<sum<<endl;
return sum;
}
void calc(int ind)
{
int w1,w2,brx=0;
cell h;
for(int i=1;i<=k;i++)
{
if(use[i])
{
w1=group[l[i]];
w2=group[r[i]];
if(get_lead2(w1)!=get_lead2(w2))
{
h.to=w2;
h.st=-1;
v[w1].push_back(h);
h.to=w1;
v[w2].push_back(h);
add2(w1,w2);
brx++;
}
}
}
for(int i=1;i<=numb;i++)
{
w1=basic_lead[i];
if(get_lead2(w1)!=get_lead2(mi[w1].to))
{
add2(w1,mi[w1].to);
h.to=w1;
h.st=mi[w1].st;
v[w1].push_back(mi[w1]);
v[mi[w1].to].push_back(h);
brx++;
}
}
for(int i=1;i<=brx;i++)rem();
otg[ind]=dfs1(get_lead2(1),0);
/*cout<<ind<<endl;
for(int i=1;i<=numb;i++)
{
w1=basic_lead[i];
cout<<w1<<endl;
for(int j=0;j<v[w1].size();j++)
{
cout<<v[w1][j].to<<" "<<v[w1][j].st<<endl;
}
cout<<endl;
}
*/
Clear();
}
void rec()
{
for(int i=0;i<(1<<k);i++)
{
int fi=i*2;
for(int j=k;j>=1;j--)
{
if(fi>=(1<<j))
{
fi-=(1<<j);
use[j]=1;
}
}
calc(i);
for(int j=1;j<=k;j++)use[j]=0;
}
}
void get_group()
{
for(int i=1;i<=n;i++)
{
group[i]=get_lead(i);
}
}
void read()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
cin>>f[i].a>>f[i].b>>f[i].c;
}
for(int i=1;i<=k;i++)
{
cin>>l[i]>>r[i];
used[l[i]]=1;
used[r[i]]=1;
}
for(int i=1;i<=n;i++)
{
cin>>br[i];
}
prec();
sort(f+1,f+m+1,cmp);
for(int i=1;i<=m;i++)
{
add1(f[i].a,f[i].b);
}
get_min_vertex();
get_basic();
get_par();
get_group();
rec();
long long int motg=0;
for(int i=1;i<(1<<k);i++)
{
motg=max(motg,otg[i]);
}
cout<<motg<<endl;
}
int main()
{
speed();
read();
return 0;
}
/*
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 'void dfs(int, int)':
toll.cpp:140:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
toll.cpp: In function 'long long int dfs1(int, int)':
toll.cpp:199:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
19024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
19024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19024 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
19024 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
19024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19024 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
19024 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
19024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19024 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
19024 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
19024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
19024 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
19024 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
