Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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.
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!
