Submission #261889

#	Time	Username	Problem	Language	Result	Execution time	Memory
261889		mayhoubsaleh	Toll (APIO13_toll)	C++14	0 / 100	2588 ms	12160 KiB

toll

#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 (stderr)

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++){
                 ~^~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22