Maximal Score Path CodeChef Solution

Problem -Maximal Score Path CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Maximal Score Path CodeChef Solution in C++17


#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define fo(n)           for(long long i = 0; i < n; i++)
#define all(v)          v.begin(),v.end() 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mkp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
 
void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
vector<int>parent, ranks;
int find(int u){
	if(parent[u]==u){
		return u;
	}
	return parent[u] = find(parent[u]);
}
void union_op(int u, int v){
	if(ranks[v]<ranks[u]){
		parent[v]=u;
	}else if(ranks[v]>ranks[u]){
		parent[u]=v;
	}else{
		parent[v] = u;
		ranks[u]++;
	}
}

void dfs(vector<vector<pair<int, int>>>&graph, int cur, int u, int v, vector<vi>&dis, vi& visited){
	if(cur == -1){
		dis[u][v] = 0;
	}else{
		dis[u][v] = cur;
	}
	visited[v]=1;
	for(auto& val:graph[v]){
		int i = val.first, w = val.second;
		if(visited[i]==0){
			int nmin = cur;
			if(cur == -1){
				nmin = w;
			}else{
				nmin = min(cur, w);
			}

			dfs(graph, nmin, u, i, dis, visited);
		}
	}
}
int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int v, e;
    cin>>v>>e;

    parent.resize(v);
    ranks.resize(v);
    fo(v){
    	parent[i]=i;
    	ranks[i]=0;
    }

    vector<vector<pair<int, int>>>graph(v);
    vector<vector<int>>edges(e, vector<int>(3, 0));
    vector<vector<int>>dis(v, vector<int>(v, 0));
    for(int i=0;i<e;i++){
    	int u, v, w;
    	cin>>u>>v>>w;
    	edges[i][0] = w;
    	edges[i][1] = u;
    	edges[i][2] = v;
    }

    // Sort it to gather edges with high weight at last
    sort(all(edges));
    int count = 0, j = e-1;

    // Make a MST with only high weight edges
    while(count!=(v-1)){
    	int u = edges[j][1], v = edges[j][2];
    	int w = edges[j][0];

    	int f = find(u);
    	int t = find(v);


    	if(f!=t){
    		count++;
    		graph[u].pb({v, w});
    		graph[v].pb({u, w});
    		union_op(f, t);
    	}
    	j--;
    }

    // Now dfs over the tree it will produce result in V^2
    for(int i=0;i<v;i++){
    	vector<int>visited(v, 0);
    	dfs(graph, -1, i, i, dis, visited);
    }


    for(int i=0;i<v;i++){
    	for(int j=0;j<v;j++){
    		printf("%d ", dis[i][j]);
    	}
    	printf("\n");
    }
    printf("\n");
}

Maximal Score Path CodeChef Solution in C++14

#include <iostream>
#include <string>
#include <vector>

#include <algorithm>
#include <utility>
#include <cmath>

typedef long long ll;

using namespace std;

int find(int x, vector<int>& parent)
{
	if (parent[x] == x)
	{
		return x;
	}

	parent[x] = find(parent[x], parent);
	return parent[x];
}

void uni(int x, int y, vector<int>& parent, vector<int>& rank)
{
	int x_rep = find(x, parent);
	int y_rep = find(y, parent);
	if (x_rep == y_rep)
	{
		return;
	}
	if (rank[x_rep] > rank[y_rep])
	{
		parent[y_rep] = x_rep;
	}
	else if (rank[x_rep] < rank[y_rep])
	{
		parent[x_rep] = y_rep;
	}
	else
	{
		parent[y_rep] = x_rep;
		rank[x_rep]++;
	}

	return;
}

void dfs(vector<vector<pair<int, int>>>& adjList, vector<vector<int>>& res, int minLen, int i, vector<bool>& visited, int st)
{
    visited[i] = true;
    if(minLen == -1)
    {
        res[st][i] = 0;
    }
    else
    {
        res[st][i] = minLen;
    }
    
    for(auto x : adjList[i])
    {
        if(visited[x.first] == false)
        {
            int newMin;
            if(minLen == -1)
            {
                newMin = x.second;
            }
            else
            {
                newMin = min(minLen, x.second);
            }
            dfs(adjList, res, newMin, x.first, visited, st);
        }
    }
    
    visited[i] = false;
    
    return;
}

int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int V, E;
	cin >> V >> E;
	vector<vector<int>> mp(E, vector<int>(3));
	for (int i = 0; i < E; i++)
	{
		cin >> mp[i][1] >> mp[i][2] >> mp[i][0];
	}

	sort(mp.begin(), mp.end());
	vector<vector<int>> res(V, vector<int>(V));
	vector<int>parent(V);
	vector<int>rank(V, 0);
	for (int i = 0; i < V; i++)
	{
		parent[i] = i;
	}
	int count = 0;
	int j = E - 1;
	vector<int> comp;
	vector<vector<pair<int, int>>> adjList(V);
	while (count != V - 1)
	{
		int u, v;
		u = mp[j][1];
		v = mp[j][2];
		if (find(u, parent) != find(v, parent))
		{
			count++;
		//	res[u][v] = mp[j][0];
		//	res[v][u] = mp[j][0];
		//	comp.push_back(j);
    		adjList[u].push_back({v, mp[j][0]});
    		adjList[v].push_back({u, mp[j][0]});
    		uni(u, v, parent, rank);
		}
		j--;
	}
    vector<bool>visited(V, false);
	for(int i = 0; i < V; i++)
	{
	    dfs(adjList, res, -1, i, visited, i);
	}
	

	for (int i = 0; i < V; i++)
	{
		for (int j = 0; j < V; j++)
		{
			cout << res[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

Maximal Score Path CodeChef Solution in C

#include<stdio.h>
#include<stdlib.h>
 
#define llu int
#define gc getchar_unlocked
#define pc putchar_unlocked
 
struct edge
{
	int from;
	
	int to;
	
	int weight;
} *edges;
 
struct vert
{
	int child;  // next child
	
	int ul_child; // ultimate child
} *list; 
 
int *parent ;
 
int ans[1005][1005];
 
inline llu getn()
{
  llu n=0, c=gc();
 
  while(c < '0' || c > '9') c = gc();
 
  while(c >= '0' && c <= '9')
   n = (n<<3) + (n<<1) + c - '0', c = gc();
 
  return n;
}
 
inline void write(llu a)
{
   char snum[20];
   int i=0;
   
   do
    {
     snum[i++]=a%10+48;
     a=a/10;
   }while(a!=0);
 
   i=i-1;
 
   while(i>=0)
    pc(snum[i--]);
 
   pc(' ');
}
 
int compare_weight(const void* i , const void *j )
{
    return (  ((struct edge*)j)->weight -  ((struct edge*)i)->weight );	
}
 
void create_set(int v)
{
	int i;
	
	for(i= 0 ; i<=v ; i++ )
	 {
	 	parent[i]=i;
	 	
		/*
	 	   parent represents the closet root of vertex
	 	*/
	 	
	 	
	 	list[i].child=0;
	 	
	 	list[i].ul_child=i;
	 }
}
 
 
int find_set(int node)
{
	if( parent[node] != node )
	 {
	 	parent[node]=find_set( parent[node] );
	 }
	 
	return parent[node]; 
}
 
 
 
void MERGE(int from , int to , int weight )
{
	int rep_from , rep_to ;
	
	
	rep_from= find_set(from);
	
	rep_to=  find_set(to);
	
	
	if( rep_from == rep_to  ) return;
	
	 
	int f = rep_from;
    
	while ( f )
	 {
        int t = rep_to;
        
	    while ( t )
		 {
            ans[t][f] = ans[f][t] = weight;
            
			t = list[t].child;
         }
        
		f = list[f].child;		
     }
     
     
     parent[rep_to]=rep_from ;
     
     list[ list[rep_from].ul_child ].child = rep_to;
     
     list[rep_from].ul_child = list[rep_to].ul_child;
}
 
 
void Merge_set(int e)
{
	int i ;
	
	for(i=0 ; i<e ; i++ )
	 { 	 
	 	 MERGE(edges[i].from,edges[i].to, edges[i].weight );
	 }
}
 
int main()
{
 
	int i , j , k , v , e , x , y , w;
	
	
	v=getn();
	
	e=getn();
 
	
	
	edges=(struct edge*)calloc(e+5,sizeof( struct edge ) );
	
	parent=( int* )calloc(v+5,sizeof(int) );
	
	 list=(struct vert*)calloc(v+5,sizeof( struct vert ) );
	
	// rank=( int* )calloc(v+5,sizeof(int) );
	
	
	for(i=0 ; i<e ; i++)
	 {
	    edges[i].from=getn()+1;
	    
	    edges[i].to=getn()+1;
	    
	    edges[i].weight=getn();
	 }
      
	 qsort( edges , e , sizeof( struct edge ) , compare_weight );
     
     
     create_set(v);
     
     Merge_set(e);
     
     
 
	 for( i=1 ; i<=v ; i++ )
      {
      	  for( j=1 ; j<=v ; j++ )
			{
				 write(ans[i][j]);
			}
			
			pc('\n'); 
      }
     
     return 0;
}

Maximal Score Path CodeChef Solution in JAVA


import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;


public class Main {

    static int[][] res;
    
    public static void main(String[] args) throws IOException {
        Scanner3 in = new Scanner3(15000000);
        //long start = System.currentTimeMillis();
        int v = in.intNext();
        int e = in.intNext();
        int[][] g = new int[v][v];
        res = new int[v][v];
        for(int[] a : g) Arrays.fill(a,INF);
        for(int[] a : res) Arrays.fill(a,-INF);
        for(int i = 0; i < e; ++i) {
            int a = in.intNext();
            int b = in.intNext();
            int w = in.intNext();
            g[a][b] = (g[b][a] = -w);
        }
        
        
        
        mst(g);
        
        
        PrintWriter pw = new PrintWriter(System.out);

        for(int i = 0; i < v; ++i) {
            for(int j = 0; j < v; ++j) {
                pw.print(res[i][j] == -INF ? 0 : -res[i][j]);
                pw.print(' ');
            }
            pw.println();
        }
        
        pw.flush();
        
        //long end = System.currentTimeMillis();
        //System.out.println(end-start);
        
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
static final int INF = 1000000000;
static int[][] mst;
    
/**
 * @param g adjacency matrix of an undirected graph, a weight of INF is interpreted as no edge,
 *        required that g[i][j] == g[j][i]
 * @return cost of mst or -1 iff graph is not connected
 */
public static int mst(final int[][] g) {
    class Edge implements Comparable<Edge> {
        public final int u,v;
        public Edge(int u,int v){this.u=u;this.v=v;}
        public int getWeight(){return g[u][v];}
        public int compareTo(Edge e){return Integer.signum(getWeight()-e.getWeight());}
    }
    
    //Initialize.
    int numVert = g.length;
    mst = new int[numVert][numVert];
    for(int i = 0; i < numVert; ++i) {
        Arrays.fill(mst[i],INF);
    }
    int cost = 0;
 
    Queue<Edge> q = new PriorityQueue<Edge>();
    boolean[] covered = new boolean[g.length];
    int numCovered = 1;
    covered[0] = true;
    for(int i = 0; i < numVert; ++i)
        if(g[0][i] != INF && !covered[i])
            q.add(new Edge(0,i));
    while(numCovered != g.length) {
        if(q.isEmpty()) return -1;
        Edge e = q.poll();
        if(!covered[e.u] || !covered[e.v]) {
            cost += e.getWeight();
            mst[e.u][e.v] = (mst[e.v][e.u] = e.getWeight());
            int newVert = covered[e.u] ? e.v : e.u;
            int oldVert = covered[e.u] ? e.u : e.v;
            covered[newVert] = true;
            ++numCovered;
            for(int i = 0; i < g[newVert].length; ++i) {
                if(i != newVert && covered[i]) {
                    res[i][newVert] = (res[newVert][i] = Math.max(e.getWeight(),res[i][oldVert]));
                }
                
                if(g[newVert][i] != INF && !covered[i])
                    q.add(new Edge(newVert,i));
            }
        }
    }
    
    return cost;
}


}







class Scanner3 {
    
    private final byte[] b;
    private int bytesRead;
    private int i = 0;
    public Scanner3(int numBytes) throws IOException {
        b = new byte[numBytes];
        int currRead = 0;
        do {
            bytesRead += currRead;
            currRead = System.in.read(b,bytesRead,b.length-bytesRead);
        } while(currRead > 0);
    }
    

            
    public void whitespaceSkip() {
        while(b[i] == ' ' || b[i] == '\r' || b[i] == '\n') ++i;
    }
    
    public int intNext() throws IOException {
        int res = 0;
        boolean negate = false;
        
        if(b[i] == '-') {
            negate = true;
            ++i;
        }
        while(b[i] >= '0' && b[i] <= '9') res = res*10+(b[i++]-'0');
        if(negate) res *= -1;
        whitespaceSkip();
        return res;
    }
    
}
Maximal Score Path CodeChef Solution Review:

In our experience, we suggest you solve this Maximal Score Path CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Maximal Score Path CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Maximal Score Path CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *