HackerEarth Decaying Roads problem solution

In this HackerEarth Decaying Roads problem solution There is a City having some set of roads where each road has the same source and the same destination.There are N trucks and M roads in the city.You are given K permits in the city(in the form of X and Y) which indicates that a truck X is permitted to travel on Road Y.

Each road has a restriction on the number of trucks it can allow to travel on it.This restricted number is known as Capacity[i].

Due to the poor condition of the roads, every year 1 particular road’s capacity reduces by a number P. The data is known for Z years.

For each year before the reduction takes place,you need to predict the maximum number of trucks that can travel in the city.

HackerEarth Decaying Roads problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll n,m,lvl[4005],s,d,ptr[4005],con,avl[4005],ans[10005],q;
struct edge
{
    ll a,b,cap,flow;
};
vector<edge>e;
vector<pair<ll,ll> >pp,qry;
vector<ll>v[4005];
void init()
{
    ll i;
    for(i=1;i<=4003;i++)
    {
        v[i].clear();
        avl[i]=0;
    }
    for(i=1;i<=10000;i++)
    {
        ans[i]=0;
    }
    e.clear();
    pp.clear();
    qry.clear();
}
void add_edge(ll a,ll b,ll cap)
{
    edge e1={a,b,cap,0};
    edge e2={b,a,0,0};
    v[a].push_back(e.size());
  e.push_back(e1);
  v[b].push_back(e.size());
  e.push_back(e2);
}
bool bfs()
{
    ll i,j,k;
    queue<ll>q;
    q.push(s);
    memset(lvl,-1,sizeof lvl);
    lvl[s]=0;
    while(!q.empty())
    {
        j=q.front();
        q.pop();
        for(k=0;k<v[j].size();k++)
        {
            ll id=v[j][k];
            ll to=e[id].b;
            if(lvl[to]==-1&&e[id].flow<e[id].cap)
            {
                lvl[to]=1+lvl[j];
                q.push(to);
            }
        }
    }
    return (lvl[d]!=-1);
}
ll dfs(ll cur,ll flow)
{
    ll i,j;
    if(cur==d)
    return flow;
    for(;ptr[cur]<v[cur].size();ptr[cur]++)
    {
        ll id=v[cur][ptr[cur]];
        ll to=e[id].b;
        if(lvl[to]!=(1+lvl[cur])||(e[id].cap-e[id].flow<=0))
        continue;
        ll f=dfs(to,min(flow,e[id].cap-e[id].flow));
        if(f>0)
        {
           e[id].flow+=f;
           e[id^1].flow-=f;
           return f;
        }
    }
    return 0;
}
ll maxflow()
{
    ll total_flow=0,j;
    while(bfs())
    {
        memset(ptr,0,sizeof ptr);
        while(1)
        {
            if(j=dfs(s,10000000000000000))
            {
                total_flow+=j;
            }
            else
            break;
        }
    }
    return total_flow;
}
void flow_ans()
{
    ll i,j,k,x,y;
    for(i=0;i<con;i++)
    {
        x=pp[i].first;
        y=pp[i].second;
        add_edge(x,n+y,1);
    }
    for(i=1;i<=n;i++)
    {
        add_edge(s,i,1);
    }
    vector<ll>eids;
    for(i=1;i<=m;i++)
    {
        add_edge(i+n,d,avl[i]);
        eids.push_back(e.size()-2);
    }
    ll prt=maxflow();
    for(i=q-1;i>=0;i--)
    {
        x=qry[i].first;
        y=qry[i].second;
        e[eids[x-1]].cap+=y;
        //cout<<e[eids[x-1]].a<<" "<<e[eids[x-1]].b<<" "<<e[eids[x-1]].cap<<"n";
        prt+=maxflow();
        //cout<<prt<<"n";
        ans[i]=prt;
    }
    for(i=0;i<q;i++)
    {
        cout<<ans[i]<<"n";
    }
}
void solve()
{
    init();
    ll i,j,ans,x,y;
    cin>>n>>m>>con;
    s=n+m+1;
    d=n+m+2;
    ans=0;
    for(i=1;i<=con;i++)
    {
        cin>>x>>y;
        pp.push_back({x,y});
    }
    for(i=1;i<=m;i++)
    {
        cin>>avl[i];
    }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>x>>y;
        qry.push_back({x,y});
        avl[x]-=y;
    }
    flow_ans();
}
int main()
{
    //freopen("samp.txt","r",stdin);
    //freopen("sout.txt","w",stdout);
    /*for(ll uu=0;uu<=9;uu++)
    {
        //string s=to_string(i);
        //string s1=to_string(i);
        stringstream ss;
        ss << uu;
        string s = ss.str();
        string s1=ss.str();
        s="in0"+s+".txt";
        s1="out0"+s1+".txt";
        freopen(s.c_str(),"r",stdin);
        freopen(s1.c_str(),"w",stdout);*/
        solve();
    //}
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int cap[5001][5001];
vector<int> graph[100001];
int r[100001];
int p[100001];
int x[100001];
int y[100001];
int capacity[100001];
vector<pair<int,int> > edges;
bool flag = 0;
bool visit[13000];
void find_augmented(int cur, int t){
    if(cur == t){
         flag = 1;
         return;
    }
    for(int i: graph[cur]){
        if(visit[i] == 0){
            if(cap[cur][i] > 0){
                edges.push_back({cur , i});
                visit[i] = 1;
                find_augmented(i , t);
                if(flag == 1){
                    break;
                }
                edges.pop_back();
            }
        }
    }
    return;
}
 
int update_augmented(){
    int mcap = cap[edges.back().first][edges.back().second];
    for(int i = 0;i < edges.size(); i++){
        mcap = min(mcap , cap[edges[i].first][edges[i].second]);
    }
    for(int i = 0; i < edges.size(); i++){
        cap[edges[i].first][edges[i].second] -= mcap;
        cap[edges[i].second][edges[i].first] += mcap;
    }
    return mcap;
}
 
int maxflow(int n,int s,int t){
    int ans = 0;
    memset(visit , 0 , sizeof(visit));
    edges.clear();
    while(1){
        flag = 0;
        find_augmented(s , t);
        if(flag == 0)
            break;
        ans += update_augmented();
        memset(visit , 0 , sizeof(visit));
        edges.clear();
    }
    return ans;
}
 
int main()
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n , m , k;
        cin >> n >> m >> k;
        for(int i = 1; i <= n; i++){
            graph[0].push_back(i);
            graph[i].push_back(0);
            cap[0][i] = 1;
        }
        for(int i = 1; i <= k; i++){
            cin >> x[i] >> y[i];
            graph[x[i]].push_back(n + y[i]);
            graph[n + y[i]].push_back(x[i]);
            cap[x[i]][n + y[i]] = 1;
        }
        for(int i = 1; i <= m; i++){
            cin >> capacity[i];
            graph[n + i].push_back(n + m + 1);
            graph[n + m + 1].push_back(n + i);
            cap[n + i][n + m + 1] = capacity[i];
        }
        int z;
        cin >> z;
        for(int i = 1; i <= z; i++){
            cin >> r[i] >> p[i];
            int idx = r[i];
            cap[idx + n][n + m + 1] -= p[i];
            assert(cap[idx + n][n + m + 1] >= 0);
        }
        int cur_flow = maxflow(n , 0 , n + m + 1);
        vector<int> ans;
        for(int i = z; i >= 1; i--){
            int idx = r[i];
            edges.clear();
            memset(visit , 0 , sizeof(visit));
            cap[idx + n][n + m + 1] += p[i];
            while(1){
                flag = 0;
                edges.clear();
                memset(visit , 0 , sizeof(visit));
                find_augmented(0 , n + m + 1);
                if(flag == 1)
                    cur_flow += update_augmented();
                else{
                    assert(edges.size() == 0);
                    break;
                }
            }
            ans.push_back(cur_flow);
        }
        while(ans.size()){
            cout << ans.back() << " " << endl;
            ans.pop_back();
        }
    }

coding problems solutions