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. #include<bits/stdc++.h>using namespace std;#define ll long long intll 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.00000001LL 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