733F codeforces - Drivers dissatisfaction

733F codeforces - Drivers dissatisfaction

Link ; https://codeforces.com/contest/733/problem/F

Solution in C++

#include <bits/stdc++.h>
using namespace std;

//Hello World

typedef long long int lli;
typedef long double ld;
#define pii pair<int,int>
#define mod 1000000007
#define S second
#define F first
#define lasB(b) (b&(-b))
#define N 200005

lli n , m , t1 , t2 , fat[N] , p[N] , p2[N][30] , deep[N] , dp[N][30] , bud ;

struct edge {lli w , c;int u , v , id;} all[N];
struct info{int v , id;};

vector<info> adj[N];
bool vis[N] , done[N];

lli fin (lli x){
    if(fat[x]!=x)
        fat[x]=fin(fat[x]);
    return fat[x];
}

bool cmp(edge a , edge b)
{
    if(a.w==b.w)return a.id<b.id;
    return a.w<b.w;
}

int maxw (int i , int j){return all[i].w<all[j].w ?j:i;}

int lca(int a , int b)
{
    if(deep[a]<deep[b])swap(a , b);
    int t = deep[a]-deep[b];
    for(int i=0;(1<<i)<=t;i++)
        if(t&(1<<i))a=p2[a][i];
    for(int i=20;i>=0;i--)
        if(p2[a][i]!=p2[b][i])
            a=p2[a][i] , b=p2[b][i];
    return a==b ?a :p2[a][0];
}

void dfs(int x, int fa)
{
    for(int i=1;i<=20;i++)
    {
        p2[x][i]=p2[p2[x][i-1]][i-1];
        dp[x][i]=maxw(  dp[x][i-1], dp[p2[x][i-1]][i-1]);
    }
    for(int i=0;i<adj[x].size();i++)
    {
        int v = adj[x][i].v , id = adj[x][i].id;
        if(v==fa)continue;
        p2[v][0]=x;
        dp[v][0]=id;
        deep[v]=deep[x]+1;
        dfs(v , x);
    }
}

int query(int a, int b) {
 int t = deep[a]-deep[b];
 int ret = 0;
 for(int i = 0; (1<<i) <= t; i++) if((1<<i)&t) {
  ret = maxw(ret, dp[a][i]);
  a = p2[a][i];
 }
 return ret;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie();
    cin>>n>>m;
    for(int i=0;i<N;i++)fat[i]=i;
    for(int i=1;i<=m;i++)cin>>all[i].w , all[i].id=i;
    for(int i=1;i<=m;i++)cin>>all[i].c;
    for(int i=1;i<=m;i++)cin>>all[i].u>>all[i].v;
    cin>>bud;
    sort(all +1, all +1+m , cmp);
    int id1=-1 , id2=-1;
    lli sum = 0;
    for(int i=1;i<=m;i++)
    {
        int u = all[i].u  , v = all[i].v , x = fin(u) , y = fin(v);
        if(x!=y)
        {
            adj[u].push_back((info){v,i});
            adj[v].push_back((info){u,i});
            fat[x]=y;
            sum+=all[i].w;
            if(id1==-1 || all[i].c<all[id1].c)id1=i;
            done[i]=1;
        }
    }
    lli ans = sum - bud /all[id1].c ;
    deep[1]=0;
    dfs(1,0);

    for(int i=1;i<=m;i++)
    {
        if(!done[i])
        {
            int u = all[i].u , v = all[i].v  ,root = lca(u,v);
            int x = maxw(query(u,root) , query(v,root));
            lli temp = sum - all[x].w + all[i].w - bud/ all[i].c;
            if(ans>temp)
            {
                ans = temp;
                id1=i;
                id2=x;
            }
        }
    }
    cout<<ans<<"\n";
    if(id2!=-1)done[id2]=0;
    done[id1]=1;
    all[id1].w-=bud/all[id1].c;
    for(int i=1;i<=m;i++)if(done[i])
        cout<<all[i].id<<" "<<all[i].w<<"\n";
    return 0;
}

Share on Google Plus

About Mohamed Sobhi

My name is Mo.Sobhy ,I study at School excelling high school in Ain Shams ,Cairo
My hobbies is programming ,and web development ,playing chess and writing horror stories.