| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 261889 |
2020-08-12T07:24:22 Z |
mayhoubsaleh |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
12160 KB |
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mid (l+r)/2
#define righ 2*i+2
#define left 2*i+1
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const ll maxn=1e5+100;
const ll inf=1e9+100;
const ll mod=1e9+7;
const ll base=17;
struct edge{
int x,y,c;
edge(int xx,int yy,int cc):x(xx),y(yy),c(cc){}
};
int n,k,m;
ll ans;
int par[maxn][base],a[maxn],dep[maxn],rd[22][2];
vector<int>v[maxn];
map<int,int>d[maxn];
vector<edge>edg;
bool com(edge a,edge b){
return a.c<b.c;
}
int root[maxn],sz[maxn];
int sub[maxn];
int getroot(int x){
if(root[x]==x)return x;
return root[x]=getroot(root[x]);
}
void mrg(int x,int y){
x=getroot(x);y=getroot(y);
if(sz[x]>sz[y])swap(x,y);
root[y]=x;
sz[x]+=sz[y];
}
void dfs(int nod,int f){
par[nod][0]=f;
sub[nod]=a[nod];
dep[nod]=1+dep[f];
for(auto x:v[nod]){
if(x==f)continue;
dfs(x,nod);
sub[nod]+=sub[x];
}
}
int jump(int x,int l){
for(int i=0;i<base;i++){
if(((1<<i)&l)!=0)x=par[x][i];
}
return x;
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
x=jump(x,dep[x]-dep[y]);
for(int i=base-1;i>=0;i--){
if(par[x][i]!=par[y][i])x=par[x][i],y=par[y][i];
}
if(x==y)return x;
return par[x][0];
}
void init(){
dfs(1,0);
for(int i=1;i<base;i++){
for(int nod=1;nod<=n;nod++){
par[nod][i]=par[par[nod][i-1]][i-1];
}
}
}
vector<edge>p[2];
void path(int x,int y){
int anc=lca(x,y);
while(x!=anc){
p[0].pb({x,par[x][0],d[par[x][0]][x]});
x=par[x][0];
}
while(y!=anc){
p[1].pb({y,par[y][0],d[y][par[y][0]]});
y=par[y][0];
}
}
int delta,dx,dy,dc;
map<int,bool>me[maxn];
void solve(){
delta=dx=dy=dc=0;
for(int i=0;i<2;i++){
int cano=0;
for(auto j:p[1-i]){
if(me[j.x][j.y])cano+=j.c;
}
int above=0;
for(auto j:p[i]){
if(me[j.x][j.y])above+=j.c;
}
int curdelta=0,under=0,underc=0;
for(auto j:p[i]){
curdelta=0;
if(me[j.x][j.y]){
under-=sub[j.x]*j.c;
above-=j.c;
}
curdelta+=sub[j.x]*j.c;
curdelta+=cano*sub[j.x];
curdelta-=above*sub[j.x];
curdelta+=under;
curdelta+=underc*sub[j.x];
if(me[j.x][j.y]){
under-=sub[j.x]*j.c;
underc+=j.c;
}
if(delta<curdelta){
delta=curdelta;
dx=j.x;dy=j.y;dc=j.c;
}
//cout<<delta<<endl;
}
}
}
void rmv(int x,int y){
for(int i=0;i<v[x].size();i++){
if(v[x][i]==y)swap(v[x][i],v[x][v[x].size()-1]);
v[x].pop_back();
}
for(int i=0;i<v[y].size();i++){
if(v[y][i]==x)swap(v[y][i],v[y][v[y].size()-1]);
v[y].pop_back();
}
}
int main() {
IOS
cin>>n>>m>>k;
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
edg.pb(edge(x,y,z));
}
for(int i=0;i<k;i++){
cin>>rd[i][0]>>rd[i][1];
}
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
root[i]=i;
sz[i]=1;
}
sort(edg.begin(),edg.end(),com);
int cnt=0;
while(cnt<n-1){
int x=edg[cnt].x,y=edg[cnt].y,c=edg[cnt].c;
if(getroot(x)==getroot(y))continue;
cnt++;
mrg(x,y);
v[x].pb(y);
v[y].pb(x);
d[x][y]=d[y][x]=c;
//cout<<x<<' '<<y<<endl;
}
bool nd=1;
for(int i=0;i<k;i++){
if(nd)init();
path(rd[i][0],rd[i][1]);
/*for(int i=0;i<2;i++){
cout<<"*********"<<endl;
for(auto ed:p[i])cout<<ed.x<<' '<<ed.y<<' '<<ed.c<<endl;
}*/
solve();
if(delta<=0){nd=0;continue;}
else{
//cout<<dx<<' '<<dy<<endl;
nd=1;
ans+=delta;
rmv(dx,dy);
v[rd[i][0]].pb(rd[i][1]);
v[rd[i][1]].pb(rd[i][0]);
d[rd[i][0]][rd[i][1]]=d[rd[i][1]][rd[i][0]]=dc;
d[dx][dy]=d[dy][dx]=0;
me[rd[i][0]][rd[i][1]]=me[rd[i][1]][rd[i][0]]=1;
}
}
cout<<ans<<endl;
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 rmv(int, int)':
toll.cpp:132:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++){
~^~~~~~~~~~~~
toll.cpp:136:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[y].size();i++){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2588 ms |
12160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2588 ms |
12160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2588 ms |
12160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2588 ms |
12160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2588 ms |
12160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
