API tools faq
paste
Advertisement
rananjali_

MY_RESOURCES

rananjali_
Oct 7th, 2022 (edited)
931
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 33.31 KB | None | 0 0
raw download clone embed print report
  1. // FLIPKART
  2.  
  3.  copy
  4. #include<bits//stdc++.h>
  5. using namespace std;
  6. #define INF 1e8
  7. bool check(char a, char b)
  8. {
  9.     if(a==b)
  10.         return 1;
  11.     if(a=='a'&&b=='o')
  12.         return 1;
  13.     if(a=='o'&&b=='a')
  14.         return 1;
  15.     if(a=='t'&&b=='l')
  16.         return 1;
  17.     if(a=='l'&&b=='t')
  18.         return 1;
  19.    return 0;
  20. }
  21.  
  22. int main()
  23. {    
  24.    int n;
  25.    cin>>n;
  26.    string draw_string;
  27.    cin>>draw_string;
  28.    string ticket[n];
  29.    for(int i=0;i<n;i++)
  30.    {
  31.       cin>>ticket[i];
  32.    }
  33.    int k;
  34.    cin>>k;
  35.    int ans=0;
  36.    for(int i=0;i<n;i++)
  37.    {  
  38.       int dp[201][201][2][2];
  39.       int sz2=draw_string.size(),sz1=ticket[i].size();
  40.       for(int j=0;j<sz1;j++)
  41.       {
  42.         dp[j][sz2][0][0]=INF;
  43.         dp[j][sz2][1][0]=INF;
  44.         dp[j][sz2][0][1]=INF;
  45.         dp[j][sz2][1][1]=INF;
  46.       }
  47.       dp[sz1-1][sz2][0][1]=0;
  48.       dp[sz1-1][sz2][1][1]=0;
  49.       for(int j=0;j<=sz2;j++)
  50.       {
  51.         dp[sz1][j][0][0]=0;
  52.         dp[sz1][j][1][0]=0;
  53.         dp[sz1][j][0][1]=0;
  54.         dp[sz1][j][1][1]=0;
  55.       }
  56.       for(int j=sz1-1;j>=0;j--)
  57.       {
  58.         for(int k=sz2-1;k>=0;k--)
  59.         {  
  60.            if(check(ticket[i][j],draw_string[k]))
  61.            {
  62.              dp[j][k][0][0]=min(dp[j+1][k+1][1][0],dp[j][k+1][0][0]);
  63.              dp[j][k][1][0]=dp[j+1][k+1][1][0];
  64.            }
  65.            else
  66.            {
  67.               dp[j][k][0][0]=dp[j][k+1][0][0];
  68.               dp[j][k][1][0]=1+dp[j][k+1][1][0];
  69.            }
  70.            if(check(ticket[i][j],draw_string[k]))
  71.            {
  72.              dp[j][k][0][1]=min(dp[j+1][k+1][1][1],dp[j][k+1][0][1]);
  73.              dp[j][k][1][1]=dp[j+1][k+1][1][1];
  74.            }
  75.            else
  76.            {
  77.               dp[j][k][0][1]=min(dp[j][k+1][0][1],dp[j+1][k+1][0][0]);
  78.               dp[j][k][1][1]=min(1+dp[j][k+1][1][1],dp[j+1][k+1][1][0]);
  79.            }
  80.         }
  81.       }
  82.       if(dp[0][0][0][1]<=k)
  83.         ans++;
  84.     }
  85.    cout<<ans<<endl;
  86.     return 0;
  87. }
  88.  
  89. ///////////////////////////////////////////
  90. bool cmp(vector<int>& a, vector<int>& b) {return a[1] < b[1];}
  91. class Solution {
  92. public:  
  93.     int findMinArrowShots(vector<vector<int>>& segments) {
  94.         sort(segments.begin(), segments.end(), cmp);
  95.         int ans = 0, arrow = 0;
  96.         for (int i = 0; i < segments.size(); i ++) {
  97.             if (ans == 0 || segments[i][0] > arrow) {
  98.                 ans ++;
  99.                 arrow = segments[i][1];
  100.             }
  101.         }
  102.         return ans;
  103.     }
  104. };
  105.  
  106.  
  107. /////////////////////////////
  108.  
  109. #include<bits/stdc++.h>
  110. using namespace std;
  111.  
  112. void solve() {
  113.     int n; cin >> n;
  114.     vector<int> v(n);
  115.     unordered_map<int, int> um;
  116.     for (int i = 0; i < n; i++) {
  117.         cin >> v[i];
  118.         um[v[i]]++;
  119.     }
  120.     int pos_sum = 0, neg_sum = 0;
  121.     for (auto &x : um) {
  122.         if (x.second == 1) {
  123.             if (x.first > 0) pos_sum += x.first;
  124.             else neg_sum += x.first;
  125.         }
  126.     }
  127.     cout << pos_sum - neg_sum << "\n";
  128. }
  129.  
  130. int main(){
  131.     solve();
  132.     return 0;
  133. }
  134.  
  135. ////////////////////////////
  136.  
  137. #include<bits/stdc++.h>
  138. using namespace std;
  139.  
  140. vector<vector<int>>dp;
  141.  
  142. int solve(vector<vector<int>>&city, int n) {
  143.  
  144.     for(int i=1;i<=n;i++) {
  145.         dp[i][0] = city[i-1][0]+ *max_element(dp[i-1].begin(),dp[i-1].end());
  146.         dp[i][1] = city[i-1][1] + dp[i-1][2];
  147.         dp[i][2] = *max_element(dp[i-1].begin(),dp[i-1].end()); //max salary till i-1th
  148.     }
  149.  
  150.     return *max_element(dp[n].begin(),dp[n].end());
  151. }
  152.  
  153. int main() {
  154.     int n,x,y;
  155.     cin>>n;
  156.     vector<vector<int>>city(n,vector<int>(2));
  157.     dp.resize(n+1,vector<int>(3));
  158.     for(int i=0;i<n;i++) {
  159.         cin>>city[i][0]>>city[i][1];
  160.     }
  161.     cout<<solve(city, n)<<endl;
  162. }
  163.  
  164.  
  165.  
  166. ////////////////////////
  167.  
  168. #include <bits/stdc++.h>
  169. #include <cstdio>
  170. #include <cstring>
  171. #include <cmath>
  172. #include <cstring>
  173. #include <chrono>
  174. #include <complex>
  175. #define endl "\n"
  176. #define ll long long int
  177. #define vi vector<int>
  178. #define vll vector<ll>
  179. #define vvi vector < vi >
  180. #define pii pair<int,int>
  181. #define pll pair<long long, long long>
  182. #define mod 1000000007
  183. #define inf 1000000000000000001;
  184. #define all(c) c.begin(),c.end()
  185. #define mp(x,y) make_pair(x,y)
  186. #define mem(a,val) memset(a,val,sizeof(a))
  187. #define eb emplace_back
  188. #define f first
  189. #define s second
  190.  
  191. using namespace std;
  192.  
  193. void dfs(int i, int par, vector<bool>&visited, vector<vector<int>>&adj)
  194. {
  195.     if(visited[i] == true)
  196.     {
  197.         visited[par] = true;
  198.         cout<<i<<par<<" ";
  199.         return;
  200.     }
  201.     for(int j : adj[i])
  202.     {
  203.         dfs(j,i,visited,adj);
  204.     }
  205. }
  206.  
  207. void solve(){
  208.     int n, p, projects, temp;
  209.     cin >> n >> p;
  210.     vector<vector<int>> adj(n+1);
  211.  
  212.     for(int i = 1; i <= n; i++) {
  213.         cin >> temp;
  214.         adj[i].push_back(temp);
  215.     }
  216.  
  217.     vector<bool>visited(n+1,false);
  218.     visited[0] = true;
  219.    
  220.     for(int i=0; i<p; i++)
  221.     {
  222.         cin >> projects;
  223.         dfs(projects,projects,visited,adj);
  224.     }
  225.  
  226.     for(int i=1; i<=n; i++)
  227.     {
  228.         if(visited[i] == false);
  229.             // cout << i << " ";
  230.     }
  231. }
  232.  
  233. int main()
  234. {    
  235.     std::ios::sync_with_stdio(false);
  236.     int T=1;
  237.     // cin >> T;
  238.     while(T--){
  239.         solve();
  240.     }
  241.     return 0;
  242. }
  243.  
  244.  
  245. /////////////////////
  246.  
  247. #include<bits/stdc++.h>
  248. #define int long long
  249. using namespace std ;
  250.  
  251. signed main()
  252. {
  253. ios_base::sync_with_stdio(false);
  254. cin.tie(NULL) ;
  255.  
  256. int n , k  ;
  257. cin >> n >> k  ;
  258. vector<int> a(n) ;
  259. for(int i = 0; i < n ; ++i)
  260.     cin >> a[i] ;
  261. int lo = 1, hi = 1e10 ;
  262. while(lo < hi)
  263. {
  264.     int mid = (lo + hi)/2  , r = 0 ;
  265.     for(int i = 0 ; i < n ; ++i)
  266.     {
  267.         r += ceil((double)a[i]/mid) ;
  268.     }
  269.  
  270.     if(r <= k)
  271.     {
  272.         hi= mid ;
  273.     }
  274.     else    
  275.         lo = mid +1 ;
  276.    
  277. }
  278. cout << hi ;
  279. }
  280.  
  281.  
  282.  
  283. /////////////////////////////////////////////////////////////////////////////////////////////
  284.  
  285.  
  286. // GRAPH ALGOS
  287.  
  288. // DIJKSTRA
  289. #include<bits/stdc++.h>
  290. using namespace std;
  291. vector<int> dijkstra(int start, int n, vector<vector<pair<int,int>>> adj){
  292.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
  293.     vector<int> dist(n,INT_MAX);
  294.     pq.push(make_pair(0,start));
  295.     dist[start] = 0;
  296.     while(!pq.empty()) {
  297.         int dst = pq.top().first;
  298.         int prev = pq.top().second;
  299.         pq.pop();
  300.         for(auto it: adj[prev]){
  301.             int next = it.first;
  302.             int nextDist = it.second;
  303.             if(dist[next] > dist[prev] + nextDist){
  304.                 dist[next] = dist[prev] + nextDist;
  305.                 pq.push(make_pair(nextDist,next));
  306.             }
  307.         }
  308.     }
  309.     return dist;
  310. }
  311.  
  312. int main(){
  313.     int n;
  314.     cin>>n;
  315.     vector<vector<pair<int,int>>> adj(n, vector<pair<int,int>>());
  316.     for(int i=0; i<n-1; i++){
  317.         int l,r,w;
  318.         cin>>l>>r>>w;
  319.         adj[l-1].push_back({r-1,w});
  320.         adj[r-1].push_back({l-1,w});
  321.     }
  322.    
  323.     int x,y,z;
  324.     cin>>x>>y>>z;
  325.     vector<int> xDis;
  326.     xDis=dijkstra(x-1, n, adj);
  327.     for(auto a:xDis) cout<<a<<" ";
  328.     return 0;
  329. }
  330. // FLOYD WARSHALL
  331.  
  332.  
  333. //Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles
  334.  
  335. void floydWarshall(int graph[][V])
  336. {
  337.    
  338.     for (i = 0; i < V; i++)
  339.         for (j = 0; j < V; j++)
  340.             dist[i][j] = graph[i][j];
  341.  
  342.    
  343.     for (k = 0; k < V; k++) {
  344.         // Pick all vertices as source one by one
  345.         for (i = 0; i < V; i++) {
  346.             // Pick all vertices as destination for the
  347.             // above picked source
  348.             for (j = 0; j < V; j++) {
  349.                 // If vertex k is on the shortest path from
  350.                 // i to j, then update the value of
  351.                 // dist[i][j]
  352.                 if (dist[i][j] > (dist[i][k] + dist[k][j])
  353.                     && (dist[k][j] != INF
  354.                         && dist[i][k] != INF))
  355.                     dist[i][j] = dist[i][k] + dist[k][j];
  356.             }
  357.         }
  358.     }
  359.  
  360.     // Print the shortest distance matrix
  361.     printSolution(dist);
  362. }
  363.  
  364. // KRUSKAL
  365.  
  366. bool sortbythird(vector<int> &A, vector<int> &B){
  367.     return A[2] < B[2];
  368. }
  369. int findParent ( int A, vector<int> &parent ) {
  370.     if( parent[A] == A ) return A;
  371.     else return findParent( parent[A], parent );
  372. }
  373. int solve(int A, vector<vector<int> > &B) {    
  374.     sort( B.begin(), B.end(), sortbythird );
  375.     vector<int> parent;
  376.     for(int i = 0; i < A; i++){
  377.         parent.push_back(i);
  378.     }
  379.     int i = 0, count = 0;
  380.     int ans = 0;
  381.     while ( i < B.size() ) {
  382.         if( findParent( B[i][0] - 1, parent ) != findParent( B[i][1] - 1, parent ) ) {
  383.             ans += B[i][2];
  384.             parent[findParent( B[i][0] - 1, parent )] = parent[findParent( B[i][1] - 1, parent )];
  385.             count++;
  386.         }
  387.         if( count == A-1 ) break;
  388.         i++;
  389.     }
  390.     return ans;
  391. }
  392.  
  393.  
  394. // TOPOLOGICAL SORTING
  395.  
  396. void Graph::topologicalSortUtil(int v, bool visited[],
  397.                                 stack<int>& Stack)
  398. {
  399.     // Mark the current node as visited.
  400.     visited[v] = true;
  401.  
  402.     // Recur for all the vertices
  403.     // adjacent to this vertex
  404.     list<int>::iterator i;
  405.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  406.         if (!visited[*i])
  407.             topologicalSortUtil(*i, visited, Stack);
  408.  
  409.     // Push current vertex to stack
  410.     // which stores result
  411.     Stack.push(v);
  412. }
  413.  
  414. // The function to do Topological Sort.
  415. // It uses recursive topologicalSortUtil()
  416. class Solution {
  417. public:
  418.     vector<int> findOrder(int N, vector<vector<int>>& P) {
  419.         vector<vector<int>> G(N);                   // {prerequisite-course : [list of next courses]}
  420.         vector<int> ans, indegree(N);               // indegree[i] denotes number of prerequisite courses for ith course
  421.         for(auto& pre : P)
  422.             G[pre[1]].push_back(pre[0]),            // forming adjacency list graph
  423.             indegree[pre[0]]++;                    
  424.        
  425.         queue<int> q;
  426.         for(int i = 0; i < N; i++)
  427.             if(indegree[i] == 0) q.push(i);         // we can start with courses having no prequisites
  428.        
  429.         while(size(q)) {
  430.             auto cur = q.front(); q.pop();
  431.             ans.push_back(cur);                     // cur has no remaining pre courses, so we can take it now
  432.             for(auto nextCourse : G[cur])
  433.                 if(--indegree[nextCourse] == 0)     // if there's a next course having 0 prequisite remaining,
  434.                     q.push(nextCourse);             // then we can take it
  435.         }
  436.         if(size(ans) == N) return ans;              // ordering exists where all courses can be finished
  437.         return {};                                      
  438.     }
  439. };
  440.  
  441.  
  442. // Level Order Traversal
  443.  
  444. vector <vector <int>> tree(n);
  445.     int k = 0;
  446.     for(int i = 0; i < nums.size(); i++){
  447.         int m = pow(2, k);
  448.         for(int j = i; j < i + m; j++) tree[k].push_back(nums[j]);
  449.         k++;
  450.         i += m-1;
  451.     }
  452.  
  453. // SIEVE
  454.  
  455. #include<bits/stdc++.h>
  456. using namespace std;
  457.  
  458. vector<int> sieve(int n){
  459.     vector<bool> is_prime(n+1, true);
  460.     is_prime[0] = is_prime[1] = false;
  461.     for (int i = 2; i <= n; i++) {
  462.         if (is_prime[i] && (long long)i * i <= n) {
  463.             for (int j = i * i; j <= n; j += i)
  464.                 is_prime[j] = false;
  465.         }
  466.     }
  467.     vector<int> ans;
  468.     for(int i=0; i<=n; i++){
  469.         if(is_prime[i]) ans.push_back(i);
  470.     }
  471.     return ans;
  472. }
  473.  
  474.  
  475. // LIS
  476. // Input --> h
  477. vector<int> ans;
  478. for(int i=0; i<h.size(); i++){
  479.     int idx=lower_bound(ans.begin(), ans.end(), h[i])-ans.begin();
  480.     if(idx==ans.size())ans.push_back(h[i]);
  481.     else ans[idx]=h[i];
  482. }
  483. return ans.size();
  484.  
  485. // WIERD ELEVATORS
  486.  
  487. #include<bits/stdc++.h>
  488. using namespace std;
  489.  
  490. int eGcd(int a, int b){
  491.     if(a==0) return b;
  492.     else return eGcd(b%a, a);
  493. }
  494. int main(){
  495.     int x,y,m;
  496.     cin>>x>>y>>m;
  497.     int hcf=eGcd(x, y);
  498.     int floorX=x/hcf;
  499.     int floorY=y/hcf;
  500.     int ans=0;
  501.     if(2>=m) cout<<-1<<'\n';
  502.     else{        
  503.         while (floorX%2 == 0)
  504.         {
  505.             ans++;
  506.             floorX /=2;
  507.         }
  508.  
  509.         for (int i=3; i*i<=floorX; i = i+2)
  510.         {
  511.             if(i>=m) cout<<-1<<'\n';
  512.             else{
  513.                 while (floorX%i ==0)
  514.                 {
  515.                     ans++;
  516.                     floorX /=i;
  517.                 }
  518.             }
  519.         }
  520.         if(floorX>2) ans++;
  521.         while (floorY%2 == 0)
  522.         {
  523.             ans++;
  524.             floorY /=2;
  525.         }
  526.  
  527.         for (int i=3; i*i<=floorY; i = i+2)
  528.         {
  529.             if(i>=m) cout<<-1<<'\n';
  530.             else{
  531.                 while (floorY%i ==0)
  532.                 {
  533.                     ans++;
  534.                     floorY /=i;
  535.                 }
  536.             }
  537.         }
  538.         if(floorY>2) ans++;
  539.         cout<<ans<<" "<<eGcd(x,y);
  540.     }
  541.     return 0;
  542. }
  543.  
  544.  
  545. // FRONTEND AND BACKEND
  546.  
  547. #include<bits/stdc++.h>
  548. using namespace std;
  549.  
  550. int main(){
  551.     int n, m;
  552.     vector <int> f = {};
  553.     vector <int> b = {};
  554.     int k = f.size();
  555.     vector <int> fd;
  556.     vector <int> bd;
  557.     int s1 = 0, s2 = 0;
  558.     for(int i = 0; i < k; i++){
  559.         if (f[i] <= b[i]){
  560.             fd.push_back(b[i]-f[i]);
  561.             s1 += f[i];
  562.         }
  563.         else{
  564.             bd.push_back(f[i]-b[i]);
  565.             s2 += b[i];
  566.         }
  567.     }
  568.     if ( (fd.size() == n) && (bd.size() == m)) return (s1 + s2);
  569.     if ( fd.size() > n){
  570.         sort(fd.begin(), fd.end());
  571.         for(int i =0; i < fd.size() -n; i++) s1 += fd[i];
  572.         return s1 + s2;
  573.     }
  574.     if ( bd.size() > m){
  575.         sort(bd.begin(), bd.end());
  576.         for(int i =0; i < bd.size() -m; i++) s1 += bd[i];
  577.         return s1 + s2;
  578.     }
  579. }
  580.  
  581.  
  582. // RUSSIAN DOLL ENVELOPE
  583.  
  584. #include<bits/stdc++.h>
  585. using namespace std;
  586.  
  587. bool comp(vector<int> &a, vector<int> &b){
  588.     if(a[0]!=b[0]) return a[0]<b[0];
  589.     return a[1]>b[1];
  590. }
  591. int solve(vector<vector<int>> v){
  592.     sort(v.begin(), v.end(), comp);
  593.     vector<int> h;
  594.     for(auto x:v){
  595.         h.push_back(x[1]);
  596.     }
  597.     vector<int> ans;
  598.     for(int i=0; i<h.size(); i++){
  599.         int idx=lower_bound(ans.begin(), ans.end(), h[i])-ans.begin();
  600.         if(idx==ans.size())ans.push_back(h[i]);
  601.         else ans[idx]=h[i];
  602.     }
  603.     return ans.size();
  604. }
  605. int main() {
  606.     int n;
  607.     cin>>n;
  608.     vector<vector<int>> v(n, vector<int>(2));
  609.     for(int i=0; i<n; i++) cin>>v[i][0]>>v[i][1];
  610.     cout<<solve(v);
  611.     return 0;
  612. }
  613.  
  614.  
  615. // BITS SEGMENT TREE
  616. #include<bits/stdc++.h>
  617. using namespace std;
  618. #define ll long long
  619.  
  620. class Segment_tree{
  621.     public:
  622.     int arr[1000]={0};
  623.     int seg[4*1000]={0};
  624.     Segment_tree(){
  625.  
  626.     }
  627.     void build(int idx, int low,int high){
  628.         if(low==high){
  629.             seg[idx]=arr[low];
  630.             return;
  631.         }
  632.         int mid=(low+high)/2;
  633.         build(2*idx+1,low,mid);
  634.         build(2*idx+2,mid+1,high);
  635.         seg[idx]=max(seg[2*idx+1],seg[2*idx+2]);
  636.     }
  637.     int query(int idx,int low,int high,int l,int r){
  638.         if(high < l || r< low)return 0;
  639.         else if(l<= low && high <=r) return seg[idx];
  640.         int mid=(low+high)/2;
  641.         int a=query(2*idx+1,low,mid,l,r);
  642.         int b=query(2*idx+2,mid+1,high,l,r);
  643.         return max(a,b);
  644.     }
  645.     void update(int idx,int low,int high,int i,int val){
  646.         if(low==high){
  647.             seg[idx]=val;return;
  648.         }
  649.         int mid=(low+high)/2;
  650.         if(i<=mid){
  651.             update(2*idx+1,low,mid,i,val);
  652.         }else{
  653.             update(2*idx+2,mid+1,high,i,val);
  654.         }
  655.         seg[idx]=max(seg[2*idx+1],seg[2*idx+2]);
  656.     }
  657. };
  658. int main()
  659. {
  660.    ll n,q;
  661.    cin>>n>>q;
  662.     vector<int> v(n);
  663.     for(int i=0;i<n;i++)cin>>v[i];
  664.     vector<Segment_tree> res(32);
  665.     for(int i=0;i<n;i++){
  666.         int x=__builtin_popcount(v[i]);
  667.         res[x].update(0,0,n-1,i,v[i]);
  668.     }
  669.     while(q--){
  670.         ll l,r,x;
  671.         cin>>l>>r>>x;
  672.         l--;r--;
  673.         int ans=res[x].query(0,0,n-1,l,r);
  674.         cout<<ans<<'\n';
  675.  
  676.     }
  677.     return 0;
  678. }
  679.  
  680. // MULTIPLYING STACKS
  681.  
  682. #include<bits/stdc++.h>
  683. using namespace std;
  684.  
  685. int main(){
  686.     stack<int> s;
  687.     int q;
  688.     cin>>q;
  689.     int sum=0, ss=0;
  690.     for(int i=0; i<q; i++){
  691.         int n, val;
  692.         cin>>n>>val;
  693.         if(n==0){
  694.             s.push(val);
  695.             sum+=val;
  696.             ss+=pow(val,2);
  697.         }
  698.         else {
  699.             int v=s.top();
  700.             s.pop();
  701.             sum-=v;
  702.             ss-=pow(v,2);
  703.         }
  704.         cout<<sum*ss<<'\n';
  705.     }
  706.     return 0;
  707. }
  708.  
  709.  
  710. // MAXIMIZE FRIENDSHIP
  711.  
  712. #include<bits/stdc++.h>
  713. using namespace std;
  714.  
  715. int dfs(int i, vector<vector<int>> v, vector<int> &vis){
  716.     vis[i]=1;
  717.     int cnt=1;
  718.     for(auto x:v[i]){
  719.         if(!vis[x]) cnt+=dfs(x, v, vis);
  720.     }
  721.     return cnt;
  722. }
  723.  
  724. int solve(int n, vector<vector<int>> v){
  725.     int ans=0;
  726.     vector<int> vis(n, 0);
  727.     for(int i=0; i<n; i++){
  728.         if(!vis[i]) {
  729.             ans=max(ans, dfs(i, v, vis));
  730.         }
  731.     }
  732.     return ans;
  733. }
  734. int main(){
  735.     int n;
  736.     cin>>n;
  737.     int m;
  738.     cin>>m;
  739.     vector<vector<int>> v(n);
  740.     vector<int> a(n);
  741.     for(int i=0; i<m; i++){
  742.         int l,r;
  743.         cin>>l>>r;
  744.         l--;
  745.         r--;
  746.         v[l].push_back(r);
  747.         v[r].push_back(l);
  748.     }
  749.     for(int i=0; i<n; i++)cin>>a[i];
  750.     int maxSize=solve(n, v);
  751.     sort(a.rbegin(),a.rend());
  752.     int p=0;
  753.     for(int i=0; i<maxSize; i++) {
  754.         p+=a[i];
  755.     }
  756.     cout<<(p*(p-1))/2;
  757.     return 0;
  758. }
  759.  
  760.  
  761. // TEACHERS AND STUDENTS
  762. #include<bits/stdc++.h>
  763. using namespace std;
  764.  
  765. int main() {
  766.     int n;
  767.     cin>>n;
  768.     vector< pair< int ,int > >T(n),S(n);
  769.     for(int i=0;i<n;i++){
  770.         cin>>S[i].first>>S[i].second;
  771.     }
  772.     for(int i=0;i<n;i++){
  773.         cin>>T[i].first>>T[i].second;
  774.     }
  775.     sort(S.begin(),S.end());
  776.     sort(T.begin(),T.end());
  777.     set< pair< pair<int ,int > ,int>>st;
  778.     for(int i=0;i<n;i++){
  779.         st.insert({{T[i].second,T[i].first},i});
  780.     }
  781.    
  782.     int i=0,j=0;
  783.     int ans=0;
  784.     for(i=0;i<n;i++){
  785.         while(T[j].first<=S[i].first){
  786.             if(T[j].first == -1){j++;continue;}
  787.             st.erase(st.find({{T[j].second,T[j].first},j}));
  788.             j++;
  789.         }
  790.         auto it = st.upper_bound({{S[i].second,S[i].first},0});
  791.         if(it!=st.end()){
  792.             ans++;
  793.             // cout<<S[i].first<<S[i].second<<" "<<T[(*it).second].first<<T[(*it).second].second<<'\n';
  794.             T[(*it).second].first=-1;
  795.             st.erase(it);
  796.         }
  797.     }
  798.     cout<<ans<<endl;
  799. }
  800.  
  801. // ODD EVEN JUMPS
  802.  
  803. #include<bits/stdc++.h>
  804. using namespace std;
  805.  
  806. vector<int> solve(vector<int>& arr){
  807.  
  808.     size_t n = arr.size();
  809.    
  810.     vector<int> smallest_geq(n, -1);
  811.     vector<int> largest_leq(n, -1);
  812.    
  813.     map<int,int> mp;
  814.     for(int i = n - 1; i >= 0; i --)
  815.     {
  816.         auto it = mp.lower_bound(arr[i]);
  817.         if(it != mp.end())
  818.         {
  819.             smallest_geq[i] = it->second;
  820.             if(it->first == arr[i])
  821.             {
  822.                 largest_leq[i] = it->second;
  823.             }
  824.         }
  825.         if(largest_leq[i] == -1 && it != mp.begin())
  826.         {
  827.             it--;
  828.             largest_leq[i] = it->second;
  829.         }
  830.         mp[arr[i]] = i;
  831.     }
  832.    
  833.     vector<vector<char>> dp(n, vector<char>(2, 0));
  834.     dp[n-1] = {1, 1};
  835.    
  836.     vector<int> ans;
  837.     ans.push_back(n-1);
  838.     for(int i = n - 2; i >= 0; i --)
  839.     {
  840.         //odd_numbered
  841.         {
  842.             int j = smallest_geq[i];
  843.             dp[i][0] = j == -1 ? 0 : dp[j][1];
  844.         }
  845.        
  846.         //even_numbered
  847.         {
  848.             int j = largest_leq[i];
  849.             dp[i][1] = j == -1 ? 0 : dp[j][0];
  850.         }
  851.        
  852.         if(dp[i][0])ans.push_back(i);
  853.     }
  854.    
  855.     return ans;
  856. }
  857.  
  858.  
  859. int main(){
  860.     int n;
  861.     cin>>n;
  862.     vector<int> v(n);
  863.     for(int i=0; i<n; i++) cin>>v[i];
  864.     vector<int> ans=solve(v);
  865.     reverse(ans.begin(),ans.end());
  866.     for(auto x:ans) cout<<x<<" ";
  867.     return 0;
  868.  
  869. }
  870.  
  871.  
  872. // MATRIX KNAPSACK
  873.  
  874. #include<bits/stdc++.h>
  875. using namespace std;
  876.  
  877. int dp[101][101][101];
  878. int helper(vector<vector<int>>& reward, vector<vector<int>>& prob, int i, int j, int currProb, int thresh){
  879. if(currProb>=thresh) return -1;
  880. if(i>=reward.size() || j>=reward[0].size()) return -1;
  881.  
  882. if(i==reward.size()-1 and j==reward[0].size()-1){
  883.     return reward[i][j];
  884. }
  885.  
  886. if(dp[i][j][currProb]!=-1) return dp[i][j][currProb];
  887.  
  888. int ma = max(helper(reward, prob,i+1,j,currProb+prob[i][j],thresh),helper(reward,prob,i,j+1,currProb+prob[i][j],thresh));
  889. if(ma==-1) return dp[i][j][currProb]=-1;
  890. return dp[i][j][currProb] = reward[i][j]+ma;
  891. }
  892.  
  893. int maxReward(vector<vector<int>>& reward, vector<vector<int>>& prob, int threshold){
  894. memset(dp,-1,sizeof(dp));
  895. return helper(reward,prob,0,0,0,threshold);
  896. }
  897.  
  898. int main(){
  899.     int n;
  900.     cin>>n;
  901.  
  902. vector<vector<int>> reward (n,vector<int>(n));
  903. vector<vector<int>> prob (n,vector<int>(n));
  904. for(int i=0;i<n;i++){
  905.     for(int j=0;j<n;j++){
  906.         cin>>reward[i][j];
  907.     }
  908. }
  909. for(int i=0;i<n;i++){
  910.     for(int j=0;j<n;j++){
  911.         cin>>prob[i][j];
  912.     }
  913. }
  914. int th;
  915. cin>>th;
  916. cout<<maxReward(reward,prob,th);
  917. for(int i=0;i<=n;i++){
  918.     for(int j=0;j<=n;j++){
  919.         for(int k=0;k<=th;k++){
  920.        
  921.         cout<<dp[i][j][k]<<" ";
  922.         }
  923.         cout<<'\n';
  924.     }
  925.     cout<<'\n';
  926. }
  927. return 0;
  928. }
  929.  
  930.  
  931.  
  932.  
  933.  
  934.  
  935.  
  936.  
  937.  
  938.  
  939.  
  940.  
  941.  
  942.  
  943.  
  944.  
  945.  
  946.  
  947.  
  948. /////////////////////////////////////////////////////// ATLASSIAN /////////////////////////////////////////////////
  949.  
  950.  
  951. // super stack
  952. #include <bits/stdc++.h>
  953. using namespace std;
  954.  
  955. void superStack(vector<string> ops) {
  956.     int n = ops.size();
  957.     vector<int> a(n), b(n);
  958.  
  959.     int k = 0;
  960.     for (string op : ops) {
  961.         stringstream strin(op);
  962.        
  963.         string optype;
  964.         strin >> optype;
  965.         if (optype == "push") {
  966.             int x;
  967.             strin >> x;
  968.             a[k++] = x;
  969.         }
  970.         if (optype == "pop") {
  971.             if (--k) b[k - 1] += b[k];
  972.             b[k] = 0;
  973.         }
  974.         if (optype == "inc") {
  975.             int x, y;
  976.             strin >> x >> y;
  977.             b[x - 1] += y;
  978.         }
  979.  
  980.         if (not k) {
  981.             cout << "EMPTY";
  982.         }
  983.         else {
  984.             cout << a[k - 1] + b[k - 1];
  985.         }
  986.         cout << " ";
  987.     }
  988. }
  989.  
  990. int main() {
  991.     vector<string> operations = {
  992.         "push 4", "pop", "push 3", "push 5", "inc 2 1",
  993.         "pop", "push 5", "push -1", "inc 1 5", "pop"
  994.     };
  995.     superStack(operations);
  996.     return 0;
  997. }
  998.  
  999.  
  1000. // MINIMISE EFFORTS
  1001. #include <bits/stdc++.h>
  1002.  
  1003. using namespace std;
  1004. #define ll long long
  1005.  
  1006. int main() {
  1007.  
  1008.     ll n;
  1009.     cin>>n;
  1010.     ll a[n+1];
  1011.    
  1012.     ll i = 1 ;
  1013.     while(i<=n){
  1014.         cin>>a[i];
  1015.         i++;
  1016.     }
  1017.      ll k;
  1018.     cin>>k;
  1019.     sort(a+1,a+n+1);
  1020.  
  1021.     ll pref[n+1]={0};
  1022.  
  1023.     i = 1 ;
  1024.     while(i<=n){
  1025.         pref[i] = pref[i-1] + a[i];
  1026.         i++;
  1027.     }
  1028.     ll my = 1e18 ;
  1029.     i = 1 ;
  1030.     while(i<=n-k+1){
  1031.  
  1032.         ll start = i ;
  1033.         ll d = k + i - 1 ;
  1034.  
  1035.         if(k%2!=0){
  1036.  
  1037.             ll md = (start+d)/2;
  1038.             //start-->md-1
  1039.  
  1040.             ll l1 = abs(md-start);
  1041.  
  1042.             ll sum1 = pref[md-1]-pref[start-1]; //pref[y]-pref[x-1]
  1043.  
  1044.             ll ans1 = abs(l1*a[md] - sum1);        
  1045.  
  1046.             //md+1-->d
  1047.  
  1048.             ll l2 = abs(d-md);
  1049.  
  1050.             ll sum2 = pref[d]-pref[md]; //pref[y]-pref[x-1]
  1051.  
  1052.             ll ans2 = abs(l2*a[md] - sum2);
  1053.  
  1054.             ll final_ans = ans1 + ans2 ;
  1055.             my = min(my,final_ans);
  1056.            
  1057.  
  1058.         } else {
  1059.             ll md1 = (start+d)/2;
  1060.             ll md2 = md1+1;          
  1061.  
  1062.             //start-->md-1
  1063.  
  1064.             ll l1 = abs(md1-start);
  1065.  
  1066.             ll sum1 = pref[md1-1]-pref[start-1]; //pref[y]-pref[x-1]
  1067.  
  1068.             ll ans1 = abs(l1*a[md1] - sum1);
  1069.             //md+1-->d
  1070.  
  1071.             ll l2 = abs(d-md1);
  1072.  
  1073.             ll sum2 = pref[d]-pref[md1]; //pref[y]-pref[x-1]
  1074.  
  1075.             ll ans2 = abs(l2*a[md1] - sum2);
  1076.  
  1077.             ll final_ans = ans1 + ans2 ;
  1078.             my = min(my,final_ans);
  1079.  
  1080.             //cout<<i<<" "<<final_ans;
  1081.             //cout<<"\n";
  1082.  
  1083.             //start-->md-1
  1084.  
  1085.             l1 = abs(md2-start);
  1086.  
  1087.             sum1 = pref[md2-1]-pref[start-1]; //pref[y]-pref[x-1]
  1088.  
  1089.             ans1 = abs(l1*a[md2] - sum1);
  1090.             //md+1-->d
  1091.  
  1092.             l2 = abs(d-md2);
  1093.  
  1094.             sum2 = pref[d]-pref[md2]; //pref[y]-pref[x-1]
  1095.  
  1096.             ans2 = abs(l2*a[md2] - sum2);
  1097.  
  1098.             final_ans = ans1 + ans2 ;
  1099.             my = min(my,final_ans);
  1100.            //  cout<<i<<" "<<final_ans;
  1101.             //cout<<"\n";
  1102.         }
  1103.         i++;
  1104.     }
  1105.  
  1106.     cout<<my
  1107.     return 0 ;
  1108. }
  1109.  
  1110.  
  1111. // MAXIMUM VALUE COUNT
  1112.  
  1113. #include <bits/stdc++.h>
  1114.  
  1115. using namespace std;
  1116. #define ll long long
  1117.  
  1118. int main(){
  1119.     int n;
  1120.     cin>>n;
  1121.     int q;
  1122.     cin>>q;
  1123.     vector<int> nums(n);
  1124.     vector<int> queries(q);
  1125.     vector<int> ans(n);
  1126.     for(int i=0; i<n; i++){
  1127.         cin>>nums[i];
  1128.     }
  1129.     for(int i=0; i<q; i++){
  1130.         cin>>queries[i];
  1131.     }
  1132.     int ctr=0;
  1133.     int maxVal=0;
  1134.     for(int i=n-1; i>=0; i--){
  1135.         if(nums[i]>maxVal){
  1136.             maxVal=nums[i];
  1137.             ctr=0;
  1138.             ctr++;
  1139.         }
  1140.         else if(nums[i]==maxVal) {
  1141.             ctr++;
  1142.         }
  1143.         ans[i]=ctr;
  1144.     }
  1145.     for(int i=0; i<q; i++){
  1146.         cout<<ans[queries[i]-1]<<" ";
  1147.     }
  1148. }
  1149.  
  1150.  
  1151. // EVALUATE EXPRESSION
  1152. #include <bits/stdc++.h>
  1153. using namespace std;
  1154.  
  1155. // Function to evaluate the logical expression
  1156. char logicalExpressionEvaluation(string str)
  1157. {
  1158.     stack<char> arr;
  1159.  
  1160.     // traversing string from the end.
  1161.     for (int i = str.length() - 1; i >= 0; i--)
  1162.     {
  1163.         if (str[i] == '[')
  1164.         {
  1165.             vector<char> s;
  1166.             while (arr.top() != ']')
  1167.             {
  1168.                 s.push_back(arr.top());
  1169.                 arr.pop();
  1170.             }
  1171.             arr.pop();
  1172.  
  1173.             // for NOT operation
  1174.             if (s.size() == 3)
  1175.             {
  1176.                 s[2] == '1' ? arr.push('0') : arr.push('1');
  1177.             }
  1178.             // for AND and OR operation
  1179.             else if (s.size() == 5)
  1180.             {
  1181.                 int a = s[2] - '0', b = s[4] - '0', c;
  1182.                 s[0] == '&' ? c = a && b : c = a || b;
  1183.                 arr.push((char)c + '0');
  1184.             }
  1185.         }
  1186.         else
  1187.         {
  1188.             arr.push(str[i]);
  1189.         }
  1190.     }
  1191.     return arr.top();
  1192. }
  1193.  
  1194. // Driver code
  1195. int main()
  1196. {
  1197.     int n;
  1198.     cin>>n;
  1199.     while(n--){
  1200.         string s;
  1201.         cin>>s;
  1202.         cout<<s;
  1203.         cout<<logicalExpressionEvaluation(s) << endl;
  1204.     }
  1205.     return 0;
  1206. }
  1207.  
  1208. // DOMINOES TILLING
  1209. #include<bits/stdc++.h>
  1210. using namespace std;
  1211. long long mod=1e9+7;
  1212. long long find(int n) {  
  1213.     vector<long long> v(n+1,0);
  1214.     v[1]=2;
  1215.     v[2]=9;  
  1216.     for(int i=3;i<=n;i++) {
  1217.         v[i]= (4%mod *v[i-1]%mod)%mod - v[i-2] + 2*pow(-1,i);
  1218.         v[i]=(v[i]+mod)%mod;
  1219.     }  
  1220.     return v[n];
  1221. }
  1222. int main() {
  1223.     for(int i=1;i<=20;i++) {
  1224.     cout<<find(i)<<" ";
  1225.     }
  1226. }
  1227.  
  1228. // CUTTING METAL SURPLUS
  1229. #include <bits/stdc++.h>
  1230.  
  1231. using namespace std;
  1232.  
  1233. int get_profit(vector<int> &rods, int sz, int cpc, int sl) {
  1234.     int profit = 0;
  1235.     for(int r : rods) {
  1236.         int rodProf = 0;
  1237.         if(r%sz == 0) {
  1238.             rodProf += ((r/sz) * sz * sl) - (r/sz - 1) * cpc;
  1239.         } else {
  1240.             rodProf += ((r/sz) * sz * sl) - (r/sz) * cpc;
  1241.         }
  1242.         if(rodProf > 0)
  1243.             profit += rodProf;
  1244.     }
  1245.     if(profit == 1913) {
  1246.         cout << sz << endl;
  1247.     }
  1248.  
  1249.     return profit;
  1250. }
  1251.  
  1252. int main() {
  1253.     int n;
  1254.  
  1255.         int cpc , sl;
  1256.     cin >> cpc >> sl;
  1257.     cin >> n;
  1258.     vector<int> v(n);
  1259.     int maxlen = 0;
  1260.     for(int i=0; i<n; i++) {
  1261.         cin >> v[i];
  1262.         maxlen = max(maxlen, v[i]);
  1263.     }
  1264.  
  1265.     int ret = 0;
  1266.     for(int sz=1; sz<=maxlen; sz++) {
  1267.         int prof = get_profit(v, sz, cpc, sl);
  1268.         ret = max(prof, ret);
  1269.     }
  1270.     cout <<ret << endl;
  1271.     return 0;
  1272.    
  1273. }
  1274.  
  1275. // SEGMENT TREE MAX VAL WITH COUNT
  1276.  
  1277. #include<bits/stdc++.h>
  1278. using namespace std;
  1279.  
  1280. vector<pair<int, int> > t;
  1281.  
  1282. pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
  1283.     if (a.first > b.first)
  1284.         return a;
  1285.     if (b.first > a.first)
  1286.         return b;
  1287.     return make_pair(a.first, a.second + b.second);
  1288. }
  1289.  
  1290. void build(vector<int> &a, int v, int tl, int tr){
  1291.     if(tl == tr) t[v]=make_pair(a[tl], 1);
  1292.     else {
  1293.         int tm=(tl+tr)/2;
  1294.         build(a, v*2+1, tl, tm);
  1295.         build(a, v*2+1+1, tm+1, tr);
  1296.         t[v]=combine(t[v*2+1], t[v*2+1+1]);
  1297.     }
  1298. }
  1299.  
  1300. pair<int, int> get_max( int v, int tl, int tr, int l, int r){
  1301.     if(l > r) return {INT_MIN,INT_MIN};
  1302.     if(l==tl && r==tr) return t[v];
  1303.     int tm=(tl+tr)/2;
  1304.     return combine(get_max(v*2+1, tl, tm, l, min(r, tm)), get_max(v*2+1+1, tm+1, tr, max(l, tm+1), r));
  1305. }
  1306.  
  1307. void update(int v, int tl, int tr, int pos, int new_val){
  1308.     if(tl==tr) t[v]=make_pair(new_val, 1);
  1309.     else{
  1310.         int tm=(tl+tr)/2;
  1311.         if(pos<=tm) update( v*2+1, tl, tm, pos, new_val);
  1312.         else update(v*2+2, tm+1, tr, pos, new_val);
  1313.         t[v]=combine(t[v*2+1], t[v*2+1+1]);
  1314.     }
  1315. }
  1316. int main() {
  1317.     int num, q;
  1318.     cin >> num>>q;    //Reading input from STDIN
  1319.     vector<int> a(num);
  1320.     vector<pair<int,int>> temp(4*num, {0,0});
  1321.     t=temp;
  1322.     for(int i=0; i<num; i++) cin>>a[i];
  1323.     build(a, 0, 0, num-1);
  1324.     for(int i=0; i<q; i++){
  1325.         char c;
  1326.         cin>>c;
  1327.         int l, r;
  1328.         cin>>l>>r;
  1329.         if(c=='q') cout<<get_max(0, 0, num-1, l-1, r-1).first<<get_max(0, 0, num-1, l-1, r-1).second<<'\n';
  1330.         else update(0, 0, num-1, l-1, r);
  1331.     }
  1332.     return 0;
  1333. }
  1334.  
  1335. // SEGMENT TREE SUM
  1336. #include <bits/stdc++.h>
  1337. using namespace std;
  1338.  
  1339. vector<int> t;
  1340.  
  1341. void build(vector<int> &a, int v, int tl, int tr){
  1342.     if(tl == tr) t[v]=a[tl];
  1343.     else {
  1344.         int tm=(tl+tr)/2;
  1345.         build(a, v*2+1, tl, tm);
  1346.         build(a, v*2+2, tm+1, tr);
  1347.         t[v]=t[v*2+1]+t[v*2+2];
  1348.     }
  1349. }
  1350.  
  1351. int sum(int v, int tl, int tr, int l, int r){
  1352.     if(l > r) return 0;
  1353.     if(l==tl && r==tr) return t[v];
  1354.     int tm=(tl+tr)/2;
  1355.     return sum(v*2+1, tl, tm, l, min(r, tm)) + sum(v*2+2, tm+1, tr, max(l, tm+1), r);
  1356. }
  1357.  
  1358. void update(int v, int tl, int tr, int pos, int new_val){
  1359.     if(tl==tr) t[v]=new_val;
  1360.     else{
  1361.         int tm=(tl+tr)/2;
  1362.         if(pos<=tm) update(v*2+1, tl, tm, pos, new_val);
  1363.         else update(v*2+2, tm+1, tr, pos, new_val);
  1364.         t[v]=t[v*2+1]+t[v*2+2];
  1365.     }
  1366. }
  1367.  
  1368. int main(){
  1369.     int n;
  1370.     cin>>n;
  1371.     vector<int> a(n);
  1372.     vector<int> arr(4*n,0);
  1373.     t=arr;
  1374.     for(int i=0; i<n; i++){
  1375.         cin>>a[i];
  1376.     }
  1377.     build(a, 0, 0, n-1);
  1378.     for(auto x:t) cout<<x<<" ";
  1379.     cout<< sum(0, 0, n-1, 2, 4);
  1380.     update (0, 0, n-1, 3, 7);
  1381.     cout<< sum(0, 0, n-1, 2, 4);
  1382.     //for(auto x:t) cout<<x<<" ";
  1383.     return 0;
  1384. }
  1385.  
  1386. // SEGMENT TREE LCM
  1387. #include <bits/stdc++.h>
  1388. using namespace std;
  1389.  
  1390. vector<int> t;
  1391.  
  1392. int gcd(int a, int b){
  1393.     if(a==0) return b;
  1394.     else return gcd(b%a, a);
  1395. }
  1396.  
  1397. int lcm(int a, int b){
  1398.     return (a*b)/gcd(a,b);
  1399. }
  1400.  
  1401. void build(vector<int> &a, int v, int tl, int tr){
  1402.     if(tl == tr) t[v]=a[tl];
  1403.     else {
  1404.         int tm=(tl+tr)/2;
  1405.         build(a, v*2+1, tl, tm);
  1406.         build(a, v*2+2, tm+1, tr);
  1407.         t[v]=lcm(t[v*2+1], t[v*2+2]);
  1408.     }
  1409. }
  1410.  
  1411. int get_lcm(int v, int tl, int tr, int l, int r){
  1412.     if(l > r) return 1;
  1413.     if(l<=tl && r>=tr) return t[v];
  1414.     int tm=(tl+tr)/2;
  1415.     return lcm(get_lcm(v*2+1, tl, tm, l, min(r, tm)), get_lcm(v*2+2, tm+1, tr, max(l, tm+1), r));
  1416. }
  1417.  
  1418. int main() {
  1419.     int num, q;
  1420.     cin >> num>>q;    //Reading input from STDIN
  1421.     vector<int> a(num);
  1422.     vector<int> temp(4*num, 0);
  1423.     t=temp;
  1424.     for(int i=0; i<num; i++) cin>>a[i];
  1425.     build(a, 0, 0, num-1);
  1426.     for(int i=0; i<q; i++){    
  1427.         int l, r;
  1428.         cin>>l>>r;
  1429.         cout<<get_lcm(0, 0, num-1, l-1, r-1)<<'\n';
  1430.     }
  1431.     return 0;
  1432. }
  1433.  
  1434.  
  1435.  
  1436. // BELLMAN FORD
  1437.  
  1438. vector<int> bellmanFord(vector<vector<int>>,int src, int V){
  1439.    
  1440.     // Step 1 - Creating a V sized array/vector,
  1441.     // and initializing it with a very big value.
  1442.    
  1443.     vector<int> dis(V,INT_MAX); // Creating a vector dis of size V with values as INT_MAX.
  1444.     dis[src] = 0; // Since we are already on source vertex, we can reach it within no time.
  1445.    
  1446.     // Step 2 - For V-1 times, traversing over,
  1447.     // all the edges and checking if a shorter
  1448.     // path between any edge u to v is possible.
  1449.     int u,v,wt;
  1450.     for(int i=0;i<V-1;i++) // Iterating V-1 times
  1451.     {
  1452.         for(int j=0;j<edges.size();j++) // Iterating over all the edges.
  1453.         {
  1454.             u = edges[j][0]; // Source vertex.
  1455.             v = edges[j][1]; // Destination vertex.
  1456.             wt = edges[j][2];// Weight of the edge.
  1457.            
  1458.             // If we can reach v from u in less time it
  1459.             // is currently required to reach v then update
  1460.             // the value.
  1461.             if(dis[u]!=INT_MAX && dis[v] > dis[u] + wt)
  1462.                 dis[v] = dis[u] + wt;
  1463.         }
  1464.     }
  1465.    
  1466.     // Step 3 - Checking for negative edge weight cycle,
  1467.     // by checking if the underliying condition satifies.
  1468.     for(int j=0;j<edges.size();j++)
  1469.     {
  1470.         u = edges[j][0];
  1471.         v = edges[j][1];
  1472.         wt = edges[j][2];
  1473.         // If the below condition satisfies, it means negative
  1474.         // edge weight cycle exists. Because traversing again
  1475.         // is reducing the cost and in order to minimize the
  1476.         // cost we can traverse till infinity and hence a proper
  1477.         // answer can't be calculated.
  1478.         if(dis[u]!=INT_MAX && dis[v] > dis[u] + wt)
  1479.             return {};
  1480.     }
  1481.     return dis; // returning our answer vector/array.
  1482. }
  1483.  
  1484.  
  1485.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!