304 North Cardinal St.
Dorchester Center, MA 02124

# Galactik Football CodeChef Solution

## Galactik Football CodeChef Solution in C++17

``````#include <bits/stdc++.h>
using namespace std;
int bfs(int source, vector<bool>&visited, vector<int> adj[], int* cost){
visited[source] = true;
queue<int>q;
int mini = INT_MAX;
q.push(source);
while(!q.empty()){
int node = q.front();
if(cost[node] >= 0) mini = min(cost[node], mini);
q.pop();
if(!visited[nbr]){
visited[nbr] = true;
q.push(nbr);
}
}
}
return mini;
}
int32_t main(){
int n, m; cin>>n>>m;
while(m--){
int u, v; cin>>u>>v; u--; v--;
}
int cost[n];
vector<int>pays;
for(int i = 0; i<n ;i++) cin>>cost[i];
vector<bool>visited(n, false);
for(int i = 0; i<n; i++){
if(!visited[i]){
}
}

int Size = pays.size();
if(Size == 1){
cout<<0;
}else if(Size == 2){
if(pays[0]  == INT_MAX || pays[1] == INT_MAX){
cout<<"-1";
return 0;
}
cout<<pays[0] + pays[1];
}else{
int ans = 0;
int Min = INT_MAX;
for(int x: pays){
if(x == INT_MAX){
cout<<"-1"; return 0;
}
ans += x;
Min = min(x, Min);
}
ans -= Min;
ans += (Size-1)*Min;
cout<<ans;
}
}``````

## Galactik Football CodeChef Solution in C++14

``````#include<bits/stdc++.h>
#define num 1000000007
#define mod 998244353
#define print(x) for(auto i:x) cout<<i<<" ";cout<<endl;
#define printa(x,st,en) for(ll i=st;i<en;i++) cout<<x[i]<<" ";cout<<endl;
#define mp make_pair
#define printm(x) for(auto i:x) cout<<i->first<<"*"<<i->second<<" ";cout<<endl;
#define pq priority_queue
#define minpq(type) pq<type,vector<type>,greater<type> >
#define printp(p) for(auto i:p) cout<<i.first<<"*"<<i.second<<" ";cout<<endl;
#define mem(a) memset(a,0,sizeof(a))
#define allof(a) a.begin(),a.end()
#define loop(i,start,end) for(ll i=start;i<end;i++)
#define deloop(i,start,end) for(ll i=start;i>end;i--)
#define testing cout<<"Test"<<endl;
#define prints(a) cout<<a<<endl;
#define vl vector<ll>
#define vb vector<bool>
#define vvl vector< vector<ll> >
#define pb push_back
#define pll pair<ll,ll>
#define vpll vector< pair<ll,ll> >
#define enter(a,begin,end) for(ll i=begin;i<end;i++) cin>>a[i];
typedef long long int ll;
using namespace std;
ll mul(ll x,ll y){
return ((x%mod)*(y%mod))%mod;
}
ll powers(ll x,ll p){
x=x%mod;
if(p==0) return 1;
if(p==1) return x%mod;
ll z=powers(x,p/2);
if(p%2) return mul(x,mul(z,z));
return mul(z,z);
}
ll dividing(ll x,ll y){
return mul(x,powers(y,mod-2));
}
ll max(ll a,ll b){
return a>b?a:b;
}
ll min(ll a,ll b){
return a<b?a:b;
}
void dfs(vvl &g,ll cur,vl &vis, ll &mini,vl &c){
vis[cur]=1;
if(c[cur]>=0){
if(mini==-1) mini=c[cur];
else mini=min(mini,c[cur]);
}
for(auto i:g[cur]){
if(!vis[i]) dfs(g,i,vis,mini,c);
}
}
void solve(){
ll n,m;
cin>>n>>m;
vvl g(n+1);
vl c(n+1);
ll x,y;
loop(i,0,m){
cin>>x>>y;
g[x].pb(y);
g[y].pb(x);
}
loop(i,1,n+1) cin>>c[i];
// print(c);
vl vis(n+1,0);
ll mini;
vl ans;
loop(i,1,n+1){
mini=-1;
if(!vis[i]){
dfs(g,i,vis,mini,c);
ans.pb(mini);
}
}
sort(ans.begin(),ans.end());
if(ans.size()==1){
cout<<"0"<<endl;
return;
}
if(ans[0]<0){
cout<<"-1"<<endl;
return;
}
ll tot=(ans.size()-1)*ans[0];
loop(i,1,ans.size()) tot+=ans[i];
cout<<tot<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt","r",stdin);
ll t=1;
// cin>>t;
while(t--) solve();
return 0;
}``````

## Galactik Football CodeChef Solution in PYTH 3

``````from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(5*(10**5))
MAX=1000000007

# 1<<3=2**3
class dsu:
def __init__(self,n):
self.parent=[i for i in range(n+1)]
self.size=[0]*(n+1)

def start(self):
for i in range(1,n+1):
self.parent[i]=i

def find(self,x):
if x!=self.parent[x]:self.parent[x]=self.find(self.parent[x])
return self.parent[x]
def union(self,u,v):
u,v=self.find(u),self.find(v)
if u!=v:
self.parent[v]=u

def treeinput(self,m):
for i in range(m):
u,v=map(int,input().split())
self.union(u,v)
def printt(self):
print(self.parent)

def main():
n,m=map(int,input().split())
d=dsu(n)
galaxy=defaultdict(list)
for i in range(m):
u,v=map(int,input().split())
d.union(u,v)
arr=[-999]
for i in range(n):
arr.append(int(input()))
for i in range(1,n+1):
galaxy[d.find(i)].append(i)
res=[]
f=1
for num in galaxy:
mn=MAX
for i in galaxy[num]:
if arr[i]>=0:
mn=min(mn,arr[i])
if mn==MAX:f=0;break
res.append(mn)
if len(galaxy)==1:print(0)
elif not f:print(-1)
else:
cnt,mn,sm=-2,MAX,0
for i in res:
mn=min(mn,i)
cnt+=1
sm+=i
print(mn*cnt+sm)
t.start()
t.join()
``````

## Galactik Football CodeChef Solution in C

``````

#include <stdio.h>

#define NMAX 100100
#define INF 1000000000

int parent[NMAX], cmin[NMAX], size[NMAX];
int N, M, C, ncc, i, j, k, sum, Cmin;

int Find(int x) {
int tx, rx;
tx = x;
while (parent[tx] > 0)
tx = parent[tx];

while (x != tx) {
rx = parent[x];
parent[x] = tx;
x = rx;
}

return tx;
}

void Union(int i, int j) {
int ti = Find(i), tj = Find(j);
if (ti == tj)
return;
ncc--;
if (size[ti] >= size[tj]) {
parent[tj] = ti;
size[ti] += size[tj];
} else {
parent[ti] = tj;
size[tj] += size[ti];
}
}

int main() {
//freopen("x.txt", "r", stdin);
scanf("%d %d", &N, &M);
ncc = N;

for (i = 1; i <= N; i++) {
cmin[i] = -1;
parent[i] = 0;
size[i] = 1;
}

for (k = 1; k <= M; k++) {
scanf("%d %d", &i, &j);
Union(i, j);
}

if (ncc == 1) {
printf("0\n");
return 0;
}

for (i = 1; i <= N; i++) {
scanf("%d", &C);
if (C < 0)
continue;
j = Find(i);
if (cmin[j] < 0 || C < cmin[j])
cmin[j] = C;
}

sum = 0;
Cmin = INF;

for (i = 1; i <= N; i++) {
if (parent[i] > 0)
continue;
if (cmin[i] < 0) {
printf("-1\n");
return 0;
}
sum += cmin[i];
if (cmin[i] < Cmin)
Cmin = cmin[i];
}

printf("%d\n", sum + (ncc - 2) * Cmin);
return 0;
}
``````

## Galactik Football CodeChef Solution in JAVA

``````import java.io.*;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;

class GalactikFootball {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;

{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
}

{
din = new DataInputStream(
new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
}

{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n') {
if (cnt != 0) {
break;
}
else {
continue;
}
}
buf[cnt++] = (byte)c;
}
return new String(buf, 0, cnt);
}

public int nextInt() throws IOException
{
int ret = 0;
while (c <= ' ') {
}
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');

if (neg)
return -ret;
return ret;
}

public long nextLong() throws IOException
{
long ret = 0;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}

public double nextDouble() throws IOException
{
double ret = 0, div = 1;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)

do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');

if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}

if (neg)
return -ret;
return ret;
}

private void fillBuffer() throws IOException
{
BUFFER_SIZE);
buffer[0] = -1;
}

{
fillBuffer();
return buffer[bufferPointer++];
}

public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}

static int min(int ...a) {
int m = a[0];
for(int i = 0; i < a.length; i++) {
if(a[i] < m) m = a[i];
}
return m;
}
static int max(int ...a) {
int m = a[0];
for(int i = 0; i < a.length; i++) {
if(a[i] > m) m = a[i];
}
return m;
}
static long solve(Vector<Integer> graph[], Vector<Integer> values) {
int n = values.size();
long total = 0;
int minValueOverall = Integer.MAX_VALUE;
Stack<Integer> st = new Stack<>();
Vector<Boolean> visited = new Vector<>();
Boolean flag = false;
int count = 0;
for(int i = 0; i < n; i++) {
}
//DFS
for(int i = 0; i < n; i++) {
if(visited.get(i)) continue;
visited.set(i, true);
st.push(i);
count++;
int minCost = Integer.MAX_VALUE;
while(!st.isEmpty()) {
int node = st.peek();
st.pop();

if(values.get(node) >= 0) {
minCost = min(minCost, values.get(node));
}

for(int j = 0; j < graph[node].size(); j++) {
int tempNode = graph[node].get(j);
if(visited.get(tempNode)) continue;
visited.set(tempNode, true);
st.push(tempNode);
}
}
if(minCost == Integer.MAX_VALUE) {
flag = true;
} else {
total += minCost;
minValueOverall = min(minValueOverall, minCost);
}
}
if(count > 1 && flag) return -1;
else if(count <= 1) return 0;
//		System.out.print("ttl " + total + " min ovl" + minValueOverall + " cnt:" + count);
long finalTotal = total - minValueOverall + minValueOverall*(count - 1);
return finalTotal;
}
public static void main(String[] args) throws IOException {
BufferedWriter output = new BufferedWriter(
new OutputStreamWriter(System.out));

int n = inpt.nextInt();
int m = inpt.nextInt();
Vector<Integer> graph[] = new Vector[n];
Vector<Integer> values = new Vector<>();
for(int i = 0; i < n; i++) {
graph[i] = new Vector<>();
}
for(int i = 0; i < m; i++) {
int temp1 = inpt.nextInt();
int temp2 = inpt.nextInt();
temp1--;
temp2--;
}
for(int i = 0; i < n; i++) {
int temp1 = inpt.nextInt();
}
long count = solve(graph, values);
output.write(String.valueOf(count));
output.flush();
}
}``````

## Galactik Football CodeChef Solution in PYPY 3

``````from collections import defaultdict as dd
import sys
sys.setrecursionlimit(10**8)
def dfs(u):
global c,d,vis,minval
for v in d[u]:
if vis[v]!=1:
#print(v)
vis[v]=1
if c[v]>=0:
minval=min(minval,c[v])
dfs(v)
return
n,m = map(int,input().split())
d=dd(list)
for _ in range(m):
a,b=map(int,input().split())
d[a].append(b)
d[b].append(a)
#print(d)
c=dd(int)
for i in range(1,n+1):
c[i]=int(input())
vis=dd(int)
s=0
grp=0
flag=0
globalmin=100000
for t in range(1,n+1):
if vis[t]!=1:
#print(t)
vis[t]=1
minval=100000
if c[t]>=0:
minval=c[t]
dfs(t)
if minval==100000:
flag=1
s=s+minval
globalmin=min(globalmin,minval)
grp=grp+1
#print(grp)
if grp==1:
print(0)
elif flag==1:
print(-1)
elif s>=0:
print((grp-2)*globalmin+s)``````

## Galactik Football CodeChef Solution in PYTH

``````st = raw_input().split()
N = int(st[0])
M = int(st[1])
G = [[x,-1] for x in range(N+1)]
for k in range(M):
st = raw_input().split()
A = int(st[0])
B = int(st[1])
if A > B:
A,B = B,A
# endif
p = G[A][0]
while G[p][0] <> p:
p = G[p][0]
# endwhile
G[A][0] = p
bp = G[B][0]
if bp <> p:
G[B][0] = p
while G[bp][0] <> bp:
bp = G[bp][0]
# endwhile
G[bp][0] = p
# endif
# endfor k
for k in range(1,N+1):
C = int(raw_input())
if C >= 0:
p = G[k][0]
while G[p][0] <> p:
p = G[p][0]
# endwhile
if (G[p][1] == -1) or (G[p][1] > C):
G[p][1] = C
# endif
# endif
# endfor k
L = []
tot = 0
mi = 0
for k in range(1,N+1):
if G[k][0] == k:
v = G[k][1]
if v == -1:
mi += 1
# endif
L.append(v)
tot += v
# endif
# endfor k
if len(L) == 1:
r = 0
else:
if mi > 0:
r = -1
else:
r = tot
L.sort()
v = L[0]*(len(L)-2)
r += v
# endif
# endif
print r
``````

## Galactik Football CodeChef Solution in C#

``````using System;
using System.Collections.Generic;
namespace C
{
class T
{
class Subset
{
public int parent;
public int rank;
public int minC;
}

static int find(Subset[] subsets, int i)
{
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

static void union(Subset[] subsets, int x, int y)
{
int xRoot = find(subsets, x);
int yRoot = find(subsets, y);

if (xRoot == yRoot)
{
return;
}

if (subsets[xRoot].rank < subsets[yRoot].rank)
{
subsets[xRoot].parent = yRoot;
subsets[yRoot].minC = ( (subsets[xRoot].minC < 0) || (subsets[yRoot].minC < 0) )
? Math.Max(subsets[xRoot].minC, subsets[yRoot].minC)
: Math.Min(subsets[xRoot].minC, subsets[yRoot].minC);
}
else if (subsets[xRoot].rank > subsets[yRoot].rank)
{
subsets[yRoot].parent = xRoot;
subsets[xRoot].minC = ( (subsets[xRoot].minC < 0) || (subsets[yRoot].minC < 0) )
? Math.Max(subsets[xRoot].minC, subsets[yRoot].minC)
: Math.Min(subsets[xRoot].minC, subsets[yRoot].minC);
}
else
{
subsets[yRoot].parent = xRoot;
subsets[xRoot].rank++;
subsets[xRoot].minC = ( (subsets[xRoot].minC < 0) || (subsets[yRoot].minC < 0) )
? Math.Max(subsets[xRoot].minC, subsets[yRoot].minC)
: Math.Min(subsets[xRoot].minC, subsets[yRoot].minC);
}
}

static void Main(string[] a)
{

int N = int.Parse(tokens[0]);
int M = int.Parse(tokens[1]);

Subset[] subsets = new Subset[N + 1];
for (int i = 1; i <= N; ++i)
{
subsets[i] = new Subset();
subsets[i].parent = i;
subsets[i].rank = 0;
}

int[,] mutual = new int[M, 2];
for (int i = 0; i < M; ++i)
{
mutual[i, 0] = int.Parse(ab[0]);
mutual[i, 1] = int.Parse(ab[1]);
}

for (int i = 1; i <= N; ++i)
{
}

for (int i = 0; i < M; ++i)
{
union(subsets, mutual[i, 0], mutual[i, 1]);
}

int count = 0, min = int.MaxValue, negatives = 0;
long sum = 0;

List<int> nodes = new List<int>();
for (int i = 1; i <= N; ++i)
{
/********
Console.WriteLine(subsets[i].parent + " " + subsets[i].rank + " " +
subsets[i].minC + "\n\n");
********/
if (subsets[i].parent == i)
{
++count;

if (subsets[i].minC < 0)
{
++negatives;
if (negatives > 1)
{
Console.WriteLine(-1);
return;
}
continue;
}

sum += subsets[i].minC;
if (min > subsets[i].minC)
{
min = subsets[i].minC;
}

}
}
/***************/
//Console.WriteLine(answer + " " + max + " " + max2);
/***************/
if (count <= 1)
{
Console.WriteLine(0);
}
else if (negatives > 0)
{
Console.WriteLine(-1);
}
else
{
//Console.WriteLine(totalTax(nodes, count));
Console.WriteLine(sum + (count - 2) * min);
}
}
}
}``````

## Galactik Football CodeChef Solution in NODEJS

``````/*
Sample

Input 1
6 6
1 2
2 3
1 3
4 5
5 6
4 6
1
3
5
2
4
6

Output 1
3

Input 2
3 1
2 3
1
-1
-1

Output 2
-1
*/
var inputBuffer = "";
process.stdin.setEncoding('utf8');
process.stdin.on('data', function (chunk) {
if (chunk.indexOf('\n') < 0) {
inputBuffer += chunk;
} else {
var lines = chunk.split(/\r\n|\n/);
var nLastLineIndex = lines.length - 1;
inputBuffer += lines[0];
processInputTextLine(inputBuffer);

for (var i = 1; i < nLastLineIndex; i++) {
processInputTextLine(lines[i]);
}

inputBuffer = lines[nLastLineIndex];
}
});
process.stdin.once('end', function () {
if (inputBuffer.length > 0) {
processInputTextLine(inputBuffer);
}
});

var lineNum = 0;
var N, M;
var unionFinder;
var taxes;

function main() {
var connectedComponentMinCost = new Array(N);
var connectedComponentCount = 0;
var i;

for (i = 0; i < N; i++) {
var root = unionFinder.root(i);
var minCost = connectedComponentMinCost[root];
if (minCost == null) {
connectedComponentCount++;
}
if (minCost == null || taxes[i] >= 0 && (minCost < 0 || minCost > taxes[i])) {
connectedComponentMinCost[root] = taxes[i];
}
}

if (connectedComponentCount > 1) {
var globalMinCost = Infinity;   // center of star
for (i = 0; i < N; i++) {
var minCost = connectedComponentMinCost[i];
if (minCost != null) {
if (minCost < 0) {
break;
}
if (globalMinCost > minCost) {
globalMinCost = minCost;
}
}
}

if (answer > 0 && connectedComponentCount > 2) {
answer += globalMinCost * (connectedComponentCount - 2)
}
}
}

function processInputTextLine(textLine) {
if (lineNum == 0) {
var splitted = textLine.split(/\s+/);
N = parseInt(splitted[0]);
M = parseInt(splitted[1])
unionFinder = new QuickUnionFind(N);
taxes = new Array(N);
} else if (lineNum <= M) {
var splitted = textLine.split(/\s+/);
unionFinder.unite(parseInt(splitted[0]) - 1, parseInt(splitted[1]) - 1);
} else if (lineNum <= M + N) {
taxes[lineNum - M - 1] = parseInt(textLine);
if (lineNum == M + N) {
main();
}
}

lineNum++;
}

function QuickUnionFind(nVertices) {
this.parentOf = new Array(nVertices);
this.connectedComponentSize = new Array(nVertices);
for (var i = 0; i < nVertices; i++) {
this.parentOf[i] = i;
this.connectedComponentSize[i] = 1;
}
}

QuickUnionFind.prototype.root = function (k) {
// loop to assign the grand parent to be the parent of k, so that we get the root of k
while (k != this.parentOf[k]) {
this.parentOf[k] = this.parentOf[this.parentOf[k]];	// path compression improvement
k = this.parentOf[k];
}
return k;
};

QuickUnionFind.prototype.unite = function (nodeIndex1, nodeIndex2) {
var r1 = this.root(nodeIndex1);
var r2 = this.root(nodeIndex2);

if (r1 != r2) {
var ccSize1 = this.connectedComponentSize[r1];
var ccSize2 = this.connectedComponentSize[r2];
var ccUnitedSize = ccSize1 + ccSize2;

if (ccSize1 <= ccSize2) {	// weighted tree size improvement
this.parentOf[r1] = r2;
this.connectedComponentSize[r2] = ccUnitedSize;
} else {
this.parentOf[r2] = r1;
this.connectedComponentSize[r1] = ccUnitedSize;
}
return true;
}

return false;
};``````

## Galactik Football CodeChef Solution in GO

``````package main

import (
"bufio"
"fmt"
"os"
)

type node struct {
visited bool
edges   []*node
cost    int
}

func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
scanner.Scan()
n := toInt(scanner.Bytes())
scanner.Scan()
m := toInt(scanner.Bytes())
graph := make([]node, n)
for i := 0; i < n; i++ {
graph[i] = node{false, nil, 0}
}
for i := 0; i < m; i++ {
scanner.Scan()
u := toInt(scanner.Bytes()) - 1
scanner.Scan()
v := toInt(scanner.Bytes()) - 1
// fmt.Println("u v", u, v)
edges := graph[u].edges
edges = append(edges, &graph[v])
graph[u].edges = edges

edges = graph[v].edges
edges = append(edges, &graph[u])
graph[v].edges = edges
}
for i := 0; i < n; i++ {
scanner.Scan()
graph[i].cost = toInt(scanner.Bytes())
if graph[i].cost < 0 {
graph[i].cost = 10001
// fmt.Println("yes", i+1)
}
}
flag := false
mins := make([]int, 1)
globalmin := 10000
for i := 0; i < n; i++ {
// fmt.Println(i+1, "node", graph[i].visited)
if !graph[i].visited {
min, count := DFSUtil(&graph[i], graph[i].cost, 0)
// fmt.Println("node ", i+1, min, count)
if min == 10001 && count < n {
flag = true
break
}
mins = append(mins, min)
if min < globalmin {
globalmin = min
}
mins[len(mins)-1] += mins[len(mins)-2]
}
}
if flag {
fmt.Println(-1)
} else if len(mins) == 2 {
fmt.Println(0)
} else if len(mins) == 3 {
fmt.Println(mins[2])
} else {
fmt.Println(mins[len(mins)-1] + globalmin*(len(mins)-3))
}
}
func DFSUtil(current *node, min int, count int) (int, int) {
current.visited = true
count++
if current.cost < min {
min = current.cost
}
// Recur for all the vertices
for i := 0; i < len(current.edges); i++ {
min, count = DFSUtil(adj, min, count)
}
}
return min, count
}

func toInt(buf []byte) (n int) {
negative := false
if buf[0] == '-' {
negative = true
for i := 1; i < len(buf); i++ {
n = n*10 + int(buf[i]-'0')
}
} else {
for i := 0; i < len(buf); i++ {
n = n*10 + int(buf[i]-'0')
}
}
if negative {
n = -n
}
return
}``````
##### Galactik Football CodeChef Solution Review:

In our experience, we suggest you solve this Galactik Football 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 Galactik Football CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Galactik Football 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!