Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Corruption in Freedonia CodeChef Solution
Problem -Corruption in Freedonia 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.
<<Previous CodeChef Problem Next Codechef Problem>>
Corruption in Freedonia CodeChef Solution in C++14
#include<bits/stdc++.h>
#define pb push_back
#define ll long long int
using namespace std;
const int mxSize = 1e6 +5;
vector<int>g[mxSize];
int vis[mxSize];
int a[mxSize],b[mxSize];
void dfs(int node){
vis[node] = 1;
bool check = false, check2 = false;
int c = 0;
for (auto it : g[node]){
if (!vis[it] ) {
check = true;
dfs(it);
c++;
a[node] += a[it];
b[node] += b[it];
if(b[node] < 0)check2 = true;
}
}
if(!check){
a[node] = 1;
}
if((!check2) && (c > 1)){
b[node] = -1;
}
}
void solve(){
int n ;
cin >> n;
for (int i = 1; i < n; i++) {
int u,v; cin >> u >> v;
g[u].pb(v); g[v].pb(u);
vis[i] = 0;
a[i] = 0;
b[i] = 0;
}
vis[0]=0;
vis[n] = 0;
a[n] = 0;
b[n] = 0;
dfs(1);
int ans = a[1] + b[1];
cout<<ans<<endl;
}
int main()
{
solve();
return 0;
}Corruption in Freedonia CodeChef Solution in PYTH 3
from sys import stdin,stdout
input=stdin.readline
n=int(input())
a=[[] for i in range(n)]
for i in range(n-1):
u,v=map(int,input().split())
a[u-1].append(v-1)
a[v-1].append(u-1)
b=[0]*n
vis=[0]*n
st=[(0,0)]
vis[0]=1
pa=[0]*n
while st:
x,y=st.pop()
b[x]=y
for i in a[x]:
if vis[i]==0:
pa[i]=x
vis[i]=1
if x==0:
st.append((i,y+len(a[x])-1))
else:
st.append((i,y+len(a[x])-2))
c=[]
for i in range(1,n):
if len(a[i])==1:
c.append((b[i],i))
c.sort()
ans=0
while c:
x,y=c.pop()
m=y
p=0
while y!=0 and pa[y]!=-1:
y=pa[y]
if pa[y]==-1:
break
if y!=0:
p+=(len(a[y])-2)
else:
p+=(len(a[y])-1)
if p>=1:
p=0
while m!=0 and pa[m]!=-1:
x=m
if pa[m]==-1:
break
m=pa[m]
pa[x]=-1
if m!=0:
p+=(len(a[m])-2)
else:
p+=(len(a[m])-1)
if y==0:
pa[0]=-1
for i in range(n):
if pa[i]!=-1:
st=[i]
pa[i]=-1
while st:
x=st.pop()
for j in a[x]:
if pa[j]!=-1:
pa[j]=-1
st.append(j)
ans+=1
print(ans)Corruption in Freedonia CodeChef Solution in C
//tree DP
//ABC036-D
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007
#define pi 3.1415926535897932384
int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int zt(int a,int b){return max(a,b)-min(a,b);}
long long llmax(long long a,long long b){if(a>b){return a;}return b;}
long long llmin(long long a,long long b){if(a<b){return a;}return b;}
long long llzt(long long a,long long b){return llmax(a,b)-llmin(a,b);}
long long llround(long long a,long long b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}
long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;}
long long lllcm(long long a,long long b){long long c=llgcd(a,b);a/=c;return a*b;}
long long llnCr(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
long long llnHr(long long a,long long b){return llnCr(a+b-1,b);}
long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
long long llpow(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
long long lldsum(long long x){long long r=0;while(x){r+=(x%10);x/=10;}return r;}
long long lldsumb(long long x,long long b){long long r=0;while(x){r+=(x%b);x/=b;}return r;}
long long llsankaku(long long x){return ((1+x)*x)/2;}
typedef struct{
int val;
int node;
}sd;
int sdsortfnc(const void *a,const void *b){
if(((sd*)a)->val > ((sd*)b)->val){return -1;}
if(((sd*)a)->val < ((sd*)b)->val){return 1;}
return 0;
}
typedef struct{
long long st;
long long fi;
long long kr;
}rs;
typedef struct{
long long st;
long long kz;
}mkj;
int sortfnc(const void *a,const void *b){
if(((rs*)a)->st == ((rs*)b)->st){return 0;}
if(((rs*)a)->st < ((rs*)b)->st){return -1;}
return 1;
}
void makemkj(rs g[],mkj x[],long long n){
long long i,ms=0,nst=g[0].st;
for(i=1;i<n;i++){
if(g[i].st!=g[i-1].st){
x[nst].kz=i-ms;
x[nst].st=ms;
nst=g[i].st;ms=i;
}
}
x[nst].kz=n-ms;
x[nst].st=ms;
}
long long dist[2097152],par[2097152];
void dfs(long long t,long long l,long long bp,rs g[],mkj x[]){
long long i;
if(dist[t]<=l){return;}
dist[t]=l;
par[t]=bp;
for(i=x[t].st;i<x[t].st+x[t].kz;i++){
dfs(g[i].fi,l+1,t,g,x);
}
}
int main(void){
long long i,j,n,m,k,a,b,c,h,w,r=0,l,t;
long long res=0;
long long dp[2097152][2]={0};
long long wa,wb;
rs g[2097152];
mkj x[2097152];
sd dat[2097152];
scanf("%lld",&n);
for(i=0;i<(n-1);i++){
scanf("%lld%lld",&a,&b);
g[2*i].st=a;
g[2*i].fi=b;
g[2*i].kr=1;
g[2*i+1].st=b;
g[2*i+1].fi=a;
g[2*i+1].kr=1;
}
qsort(g,2*(n-1),sizeof(g[0]),sortfnc);
makemkj(g,x,2*(n-1));
for(i=0;i<=n;i++){
dist[i]=inf;
}
dfs(1,0,-1,g,x);
for(i=0;i<n;i++){
dat[i].node=i+1;
dat[i].val=dist[i+1];
}
qsort(dat,n,sizeof(dat[0]),sdsortfnc);
for(i=0;i<n;i++){
w=dat[i].node;
wa=1;
for(j=x[w].st;j<x[w].st+x[w].kz;j++){
if(par[w]==g[j].fi){continue;}
wa=wa+dp[g[j].fi][0]-1;
}
dp[w][0]=wa;
if(x[w].kz==1 && g[x[w].st].fi==par[w]){dp[w][1]=0;}
else{
wa=0;h=-llinf;
wb=0;t=0;
for(j=x[w].st;j<x[w].st+x[w].kz;j++){
if(par[w]==g[j].fi){continue;}
wa+=dp[g[j].fi][0];
h=llmax(dp[g[j].fi][1]-dp[g[j].fi][0],h);
if(dp[g[j].fi][0]<=dp[g[j].fi][1]){t=1;}
wb+=llmax(dp[g[j].fi][0],dp[g[j].fi][1]);
}
if(t==1){dp[w][1]=wb;}
else{dp[w][1]=wa+h;}
}
//printf("%lld %lld %lld\n",w,dp[w][0],dp[w][1]);
}
printf("%lld\n",llmax(dp[1][0],dp[1][1]));
return 0;
}Corruption in Freedonia CodeChef Solution in JAVA
import java.util.*;
class Test
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
ArrayList<Integer>[] array = (ArrayList<Integer>[])new ArrayList[n+1];
for(int i=1; i<=n; i++)
array[i] = new ArrayList<Integer>();
for(int i=0; i<n-1; i++)
{
int a = scan.nextInt();
int b = scan.nextInt();
array[a].add(b);
array[b].add(a);
}
int dp[] = new int[n+1];
dfs(array, new boolean[n+1], 1, dp);
System.out.println(Math.max(dp[1], 1));
}
public static void dfs(ArrayList<Integer>[] array, boolean[] visited, int curr, int[] dp)
{
if(visited[curr] == false)
{
visited[curr] = true;
for(int u : array[curr])
{
dfs(array, visited, u, dp);
}
visited[curr] = false;
}
int s1 = 0;
int count = 0;
if(visited[curr] == false)
{
for(int u : array[curr])
{
if(visited[u] == false)
s1 = s1 + Math.max(dp[u], 1);
}
}
if(visited[curr] == false)
{
for(int u : array[curr])
{
int s2 = 0;
if(visited[u] == false)
s2 = s1 - Math.max(dp[u], 1) + dp[u];
count = Math.max(count, s2);
}
}
dp[curr] = count;
return;
}
}Corruption in Freedonia CodeChef Solution in GO
package main
import (
"bufio"
"fmt"
"os"
)
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] != ' ' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readNum(scanner *bufio.Scanner) (a int) {
scanner.Scan()
readInt(scanner.Bytes(), 0, &a)
return
}
func readTwoNums(scanner *bufio.Scanner) (a int, b int) {
res := readNNums(scanner, 2)
a, b = res[0], res[1]
return
}
func readNNums(scanner *bufio.Scanner, n int) []int {
res := make([]int, n)
x := 0
scanner.Scan()
for i := 0; i < n; i++ {
for x < len(scanner.Bytes()) && scanner.Bytes()[x] == ' ' {
x++
}
x = readInt(scanner.Bytes(), x, &res[i])
}
return res
}
func fillNNums(scanner *bufio.Scanner, n int, res []int) {
x := 0
scanner.Scan()
for i := 0; i < n; i++ {
for x < len(scanner.Bytes()) && scanner.Bytes()[x] == ' ' {
x++
}
x = readInt(scanner.Bytes(), x, &res[i])
}
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] != ' ' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt64(bytes []byte, from int, val *int64) int {
i := from
var tmp int64
for i < len(bytes) && bytes[i] != ' ' {
tmp = tmp*10 + int64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readNInt64Nums(scanner *bufio.Scanner, n int) []int64 {
res := make([]int64, n)
x := -1
scanner.Scan()
for i := 0; i < n; i++ {
x = readInt64(scanner.Bytes(), x+1, &res[i])
}
return res
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
N := readNum(scanner)
edges := make([][]int, N-1)
for i := 0; i < N-1; i++ {
edges[i] = readNNums(scanner, 2)
}
fmt.Println(solve(N, edges))
}
func solve(N int, edges [][]int) int {
dp := make([]int, N)
outs := make([][]int, N)
for i := 0; i < N; i++ {
outs[i] = make([]int, 0, 10)
}
for _, edge := range edges {
u, v := edge[0]-1, edge[1]-1
outs[u] = append(outs[u], v)
outs[v] = append(outs[v], u)
}
var dfs func(p, u int)
dfs = func(p, u int) {
for _, v := range outs[u] {
if p == v {
continue
}
dfs(u, v)
}
x := -1
for _, v := range outs[u] {
if p == v {
continue
}
if x == -1 || dp[v] > dp[x] {
x = v
}
}
for _, v := range outs[u] {
if p == v {
continue
}
if x != v {
dp[u] += max(dp[v], 1)
} else {
dp[u] += dp[v]
}
}
}
dfs(-1, 0)
return max(dp[0], 1)
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}
func solve1(N int, edges [][]int) int {
if N <= 2 {
return 1
}
degree := make([]int, N)
for _, edge := range edges {
u, v := edge[0]-1, edge[1]-1
degree[u]++
degree[v]++
}
outs := make([][]int, N)
for i := 0; i < N; i++ {
outs[i] = make([]int, 0, degree[i])
}
for _, edge := range edges {
u, v := edge[0]-1, edge[1]-1
outs[u] = append(outs[u], v)
outs[v] = append(outs[v], u)
}
var dfs func(p, u int) int
var total int
var pp int
dfs = func(p, u int) int {
leaf := true
r := 1
for _, v := range outs[u] {
if p == v {
continue
}
leaf = false
x := dfs(u, v)
if x > 1 {
r = 2
}
}
if leaf {
total++
} else if r == 1 {
if u == 0 && degree[u] > 1 {
pp++
} else if degree[u] > 2 {
pp++
}
}
if r > 1 {
return r
}
return degree[u] - 1
}
dfs(-1, 0)
return total - pp
}Corruption in Freedonia CodeChef Solution Review:
In our experience, we suggest you solve this Corruption in Freedonia 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 Corruption in FreedoniaCodeChef Solution.
Conclusion:
I hope this Corruption in Freedonia 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!
