Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Path-etic Sums CodeChef Solution
Problem -Path-etic Sums 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.
Path-etic Sums CodeChef Solution in C++17
#include"bits/stdc++.h"
#define nl '\n'
using namespace std;
typedef long long ll;
const int N = 105;
vector<int>g[N];
int ans[N];
void dfs(int u, int par, int s) {
if(s%2) {
ans[u] = 2;
}
else ans[u] = 1;
for(auto v : g[u]) {
if(v != par) {
dfs(v, u, s + 1);
}
}
}
void solve() {
memset(ans, 0, sizeof ans);
memset(g, 0, sizeof g);
int n; cin >> n;
for(int i = 1; i <= n - 1; i++) {
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, -1, 1);
for(int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
cout << nl;
}
int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
int t = 1;
cin >> t;
for(int i = 1; i <= t; i++) {
// cout << "Case " << i << ": ";
solve();
}
return 0;
} Path-etic Sums CodeChef Solution in C++14
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define el '\n'
using namespace std;
const int N = 105;
vector<int>g[N];
int col[N];
bool vis[N];
void dfs(int u){
vis[u]=1;
for(int i = 0;i<g[u].size();i++){
int v = g[u][i];
if(!vis[v]){
col[v]=col[u]^1;
dfs(v);
}
}
}
void solve(){
int n,m,i,j,u,v;
cin>>n;
for(i=1;i<=n;i++){
g[i].clear();vis[i]=0;col[i]=0;
}
for(i=1;i<n;i++){
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1);
for(i=1;i<=n;i++){
if(col[i]==0) cout<<2<<' ';
else cout<<1<<' ';
}
cout<<el;
}
int main(){
int tc;
cin>>tc;
while(tc--){
solve();
}
}Path-etic Sums CodeChef Solution in PYTH 3
# cook your dish here
from collections import defaultdict
def solve(n,adj):
color = [0] * n
def dfs(i,curr):
color[i-1] = curr
for nei in adj[i]:
if color[nei-1] > 0:
continue
dfs(nei,curr ^ 3)
for i in range(1,n+1):
if color[i-1] > 0:
continue
dfs(i,1)
return ' '.join(map(str,color))
for _ in range(int(input())):
adj = defaultdict(set)
n = int(input())
for _ in range(n-1):
u,v = list(map(int,input().split()))
adj[u].add(v)
adj[v].add(u)
print(solve(n,adj))Path-etic Sums CodeChef Solution in C
#include<stdio.h>
#include<stdlib.h>
int **adj;
int *ans;
int n;
void assign(int l,int p);
int main()
{
int i,t;
scanf("%d",&t);
for(i=0;i<t;i++)
{
int j,u,v;
scanf("%d",&n);
adj=(int **)calloc(n,sizeof(int *));
ans=(int *)calloc(n,sizeof(int));
for(j=0;j<n;j++)
{
adj[j]=(int *)calloc(n,sizeof(int));
}
for(j=0;j<n-1;j++)
{
scanf("%d%d",&u,&v);
adj[u-1][v-1]=1;
adj[v-1][u-1]=1;
}
ans[0]=4;
for(j=1;j<n;j++)
{
if(adj[0][j]==1)
{
adj[j][0]=-1;
assign(1,j);
}
}
for(j=0;j<n;j++)
printf("%d ",ans[j]);
printf("\n");
free(adj);
free(ans);
}
return 0;
}
void assign(int l,int p)
{
int j;
if(l%2==0)
ans[p]=4;
else
ans[p]=5;
l=l+1;
for(j=0;j<n;j++)
{
if(adj[p][j]==1)
{
adj[j][p]=-1;
assign(l,j);
}
}
return;
}Path-etic Sums CodeChef Solution in JAVA
import java.io.*;
import java.util.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter write = new BufferedWriter(new OutputStreamWriter(System.out));
long ts = Long.parseLong(read.readLine().trim());
for (int it = 1; it <= ts; it++) {
// long n = Long.parseLong(read.readLine().trim());
int n = Integer.parseInt(read.readLine());
// int [] ar = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// String string = read.readLine().trim();
// String[] binary = read.readLine().split("");
// String[] string = read.readLine().split(" ");
// int n = Integer.parseInt(string[0]);
// int k = Integer.parseInt(string[1]);
// int y = Integer.parseInt(string[2]);
// int z = Integer.parseInt(string[3]);
// int [] array = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// int[][] mat = new int[n + 1][n + 1];
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for (int i = 0; i <= n; i++) list.add(new ArrayList<>());
for (int i = 0; i < n - 1; i++) {
String[] str = read.readLine().split(" ");
int x = Integer.parseInt(str[0]);
int y = Integer.parseInt(str[1]);
list.get(x).add(y);
list.get(y).add(x);
// mat[x][y] = mat[y][x] = w;
}
level = new int[n+1];
level[1] = 1;
dfs(list,1,-1,1);
for (int i = 1; i <= n; i++) {
if(level[i]%2== 0)
write.write("1 ");
else
write.write("2 ");
}
write.write("\n");
}
write.flush();
write.close();
read.close();
}
private static void dfs(ArrayList<ArrayList<Integer>> list, int node, int parent, int lev) {
level[node] = lev;
for(int a : list.get(node)){
if(a!=parent){
dfs(list,a,node,lev+1);
}
}
}
private static int[] level;
}Path-etic Sums CodeChef Solution in PYPY 3
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import *
from functools import *
from itertools import *
from heapq import *
import sys,math
input = sys.stdin.readline
def answer():
N = int(input())
e = [[] for _ in range(N)]
for _ in range(N-1):
u,v = map(int,input().split())
u -= 1
v -= 1
e[u].append(v)
e[v].append(u)
A = [-1]*N
v = deque()
A[0]=1
v.append(0)
while v:
x = v.popleft()
if A[x]==1:
res = 2
else:
res = 1
for ix in e[x]:
if A[ix]!=-1:
continue
A[ix] = res
v.append(ix)
print(*A)
for _ in range(int(input())):
answer()Path-etic Sums CodeChef Solution in PYTH
'''input
2
7
1 2
4 6
3 5
1 4
7 5
5 1
3
1 2
2 3
'''
from bisect import bisect_right as bl
from random import randint as R
RI = lambda : [int(_x) for _x in raw_input().split()]
for _ in range(input()):
n = input()
C = [[] for i in range(n)]
for i in range(n-1):
a,b = RI()
a-=1
b-=1
C[a].append(b)
C[b].append(a)
V = [0]*n
def dfs(root=0,par = -1,h=0):
V[root] = 1+h
for i in C[root]:
if i != par:
dfs(i,root,h^1)
dfs()
for i in range(n):
print V[i],
print
Path-etic Sums CodeChef Solution in C#
using System;
using System.Collections.Generic;
using System.Linq;
public class Test
{
public static void Main()
{
var t = int.Parse(Console.ReadLine().Trim());
while(t-- > 0)
{
var n = int.Parse(Console.ReadLine().Trim());
var neighbors = new List<int>[n+1];
for(int i = 0; i < neighbors.Length; i++)
{
neighbors[i] = new List<int>();
}
for (int i = 0; i < n-1; i++)
{
var edge = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
var a = edge[0];
var b = edge[1];
neighbors[a].Add(b);
neighbors[b].Add(a);
}
var divisor = 103;
var queue = new Queue<Tuple<int, int>>();
queue.Enqueue(Tuple.Create(1, 0));
var values = new int[n+1];
var visited = new bool[n + 1];
values[1] = divisor;
while (queue.Any())
{
var current = queue.Dequeue();
var id = current.Item1;
var dist = current.Item2;
foreach(var neighbor in neighbors[id])
{
if (visited[neighbor])
continue;
visited[neighbor] = true;
values[neighbor] = divisor + ((dist + 1) % 2);
queue.Enqueue(Tuple.Create(neighbor, dist + 1));
}
}
Console.WriteLine(string.Join(" ", values.Skip(1).Take(n)));
}
}
}Path-etic Sums CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
tc := readNum(reader)
var buf bytes.Buffer
for tc > 0 {
tc--
n := readNum(reader)
E := make([][]int, n-1)
for i := 0; i < n-1; i++ {
E[i] = readNNums(reader, 2)
}
res := solve(n, E)
for i := 0; i < n; i++ {
buf.WriteString(fmt.Sprintf("%d ", res[i]))
}
buf.WriteByte('\n')
}
fmt.Print(buf.String())
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func solve(n int, E [][]int) []int {
G := getGraph(n, E)
color := make([]int, n)
var dfs func(p, u int)
dfs = func(p, u int) {
for _, v := range G[u] {
if p == v {
continue
}
color[v] = 1 - color[u]
dfs(u, v)
}
}
dfs(-1, 0)
res := make([]int, n)
for i := 0; i < n; i++ {
if color[i] == 1 {
res[i] = 2
} else {
res[i] = 3
}
}
return res
}
func getGraph(n int, E [][]int) [][]int {
degree := make([]int, n)
for _, e := range E {
u, v := e[0]-1, e[1]-1
degree[u]++
degree[v]++
}
adj := make([][]int, n)
for i := 0; i < n; i++ {
adj[i] = make([]int, 0, degree[i])
}
for _, e := range E {
u, v := e[0]-1, e[1]-1
adj[u] = append(adj[u], v)
adj[v] = append(adj[v], u)
}
return adj
}Path-etic Sums CodeChef Solution Review:
In our experience, we suggest you solve this Path-etic Sums 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 Path-etic Sums CodeChef Solution.
Conclusion:
I hope this Path-etic Sums 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!
