| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1109361 |
2024-11-06T14:51:44 Z |
vivkostov |
Toll (APIO13_toll) |
C++14 |
|
42 ms |
17144 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],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],dpmi[200005],dpbr[200005],used1[100005],bin[100005][30];
poin f[300005];
vector<cell>v[100005];
vector<cell>vert[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];
}
}
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_lead2(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 brx)
{
int a,b;
for(int i=1;i<=brx;i++)
{
a=s.top().first,b=s.top().second;
sz[a]-=sz[b];
num[a]-=num[b];
lead[b]=b;
s.pop();
}
}
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 Clear()
{
int w;
for(int i=1;i<=numb;i++)
{
w=basic_lead[i];
v[w].clear();
dpbr[w]=0;
dpmi[w]=inf;
}
memset(used1,0,sizeof(used1));
}
void get_group()
{
for(int i=1;i<=n;i++)
{
group[i]=get_lead(i);
}
}
void fill_vert()
{
int w1,w2,brx=0;
cell h;
for(int i=1;i<=m;i++)
{
w1=group[f[i].a];
w2=group[f[i].b];
if(get_lead2(w1)!=get_lead2(w2))
{
h.to=w2;
h.st=f[i].c;
vert[w1].push_back(h);
h.to=w1;
vert[w2].push_back(h);
add2(w1,w2);
brx++;
}
}
rem(brx);
/*cout<<numb<<endl;
for(int i=1;i<=numb;i++)
{
cout<<basic_lead[i]<<endl;
for(int j=0;j<vert[basic_lead[i]].size();j++)
{
cout<<vert[basic_lead[i]][j].to<<" "<<vert[basic_lead[i]][j].st<<endl;
}
cout<<endl;
}
cout<<endl;
*/
}
void prec1()
{
for(int i=1;i<=numb;i++)
{
bin[i][0]=i;
}
}
void make_bin_lifting(int beg,int par,int step)
{
int w;
bin[beg][step]=bin[bin[beg][step-1]][step-1];
}
long long int dfs1(int beg,int p)
{
long long int sum=0,w;
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);
dpbr[beg]+=dpbr[w];
dpmi[beg]=min(dpmi[beg],dpmi[w]);
if(v[beg][i].st==-1)
{
sum+=dpbr[w]*dpmi[w];
}
}
if(beg==group[1])
{
//cout<<beg<<endl;
memset(used1,0,sizeof(used1));
}
}
for(int i=0;i<vert[beg].size();i++)
{
if(!used1[vert[beg][i].to])
{
dpmi[beg]=min(dpmi[beg],vert[beg][i].st);
}
}
//cout<<dpbr[beg]<<" "<<dpmi[beg]<<" "<<beg<<" "<<sum<<endl;
used1[beg]=1;
return sum;
}
void calc(int ind)
{
int w1,w2,brx=0,lamp=0;
cell h;
for(int i=1;i<=k;i++)
{
if(use[i])
{
w1=get_lead2(l[i]);
w2=get_lead2(r[i]);
if(w1!=w2)
{
h.to=group[r[i]];
h.st=-1;
v[group[l[i]]].push_back(h);
h.to=group[l[i]];
v[group[r[i]]].push_back(h);
add2(w1,w2);
brx++;
}
else
{
lamp=1;
}
}
}
int bl1,bl2;
//cout<<numb<<endl;
for(int i=1;i<=numb;i++)
{
bl1=basic_lead[i];
for(int j=0;j<vert[bl1].size();j++)
{
bl2=vert[bl1][j].to;
w1=get_lead2(bl1);
w2=get_lead2(bl2);
if(w1!=w2)
{
h.to=bl2;
h.st=vert[bl1][j].st;
v[bl1].push_back(h);
h.to=bl1;
v[bl2].push_back(h);
add2(w1,w2);
brx++;
}
}
}
rem(brx);
if(!lamp)otg[ind]=dfs1(group[1],0);
/*cout<<endl;
cout<<ind<<endl;
for(int i=1;i<=numb;i++)
{
cout<<basic_lead[i]<<endl;
for(int j=0;j<v[basic_lead[i]].size();j++)
{
cout<<v[basic_lead[i]][j].to<<" "<<v[basic_lead[i]][j].st<<endl;
}
cout<<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;
}
else use[j]=0;
}
calc(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_basic();
get_group();
fill_vert();
Clear();
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 make_bin_lifting(int, int, int)':
toll.cpp:160:9: warning: unused variable 'w' [-Wunused-variable]
160 | int w;
| ^
toll.cpp: In function 'long long int dfs1(int, int)':
toll.cpp:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for(int i=0;i<v[beg].size();i++)
| ~^~~~~~~~~~~~~~
toll.cpp:186:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for(int i=0;i<vert[beg].size();i++)
| ~^~~~~~~~~~~~~~~~~
toll.cpp: In function 'void calc(int)':
toll.cpp:228:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
228 | for(int j=0;j<vert[bl1].size();j++)
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16976 KB |
Output is correct |
| 2 |
Correct |
3 ms |
17144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16976 KB |
Output is correct |
| 2 |
Correct |
3 ms |
17144 KB |
Output is correct |
| 3 |
Incorrect |
42 ms |
17064 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16976 KB |
Output is correct |
| 2 |
Correct |
3 ms |
17144 KB |
Output is correct |
| 3 |
Incorrect |
42 ms |
17064 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16976 KB |
Output is correct |
| 2 |
Correct |
3 ms |
17144 KB |
Output is correct |
| 3 |
Incorrect |
42 ms |
17064 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16976 KB |
Output is correct |
| 2 |
Correct |
3 ms |
17144 KB |
Output is correct |
| 3 |
Incorrect |
42 ms |
17064 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
