Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Decaying Roads problem solution

YASH PAL, 31 July 2024
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

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

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes