King Killing CodeChef Solution | May Long Challenge | KKLING

Share:

king killing codechef solutionView on Codechef.

king killing codechef solution

In a faraway kingdom there are NN cities numbered 11 to NN connected to each other in the form of a tree. The city numbered 11 is the kingdom where the king resides. A city is called a leaf if it is not the kingdom and it has exactly one adjacent city. Each leaf city has an assassin.

The enemies of the king have announced a huge reward for the assassination of the king. Each assassin starts moving from his current city following the shortest path to the kingdom. It takes exactly 11 day for an assassin to move to an adjacent city..

The assassins don’t want to split the reward, so if an assassin AA encounters any other assassin BB ahead of him on the same path that AA is supposed to follow (no matter how far ahead), then AA uses his magical power to attack BB.

After all the magical powers were used, every assassin who was attacked dies. Suppose AA is a living assassin who attacked somebody. Now, AA will move directly to the position of the assassin closest to the kingdom that AA attacked, with the cost of 11 day. If there are multiple assassins in the same city simultaneously, they form a pact not to kill each other and start moving together. Once an assassin reaches the kingdom, he cannot be killed anymore, since he can kill the king, take the reward, and leave.

Your task is to find which assassin will reach the kingdom first and in how many days. If more than one assassin reaches the kingdom simultaneously, output all of them in sorted order. Each assassin is represented by the number of the city where they started from.

Input

  • The first line contains an integer TT, the number of test cases
  • The first line of every test case contains a single integer NN, the number of cities.
  • Each of the next N−1N−1 lines contains two integers uu and vv denoting that city uu is connected to city vv.

Output

  • For every test case, the first line should contain KK and TT, the number of assassins who are first to reach and the number of days required.
  • In the next line print KK space-separated integers denoting the assassins who are first to reach the kingdom in sorted order.

Constraints

  • 1≤T≤1051≤T≤105
  • 3≤N≤2⋅1053≤N≤2⋅105
  • 1≤u,v≤N1≤u,v≤N
  • The sum of NN over all test cases does not exceed 106106
  • The connections form a tree structure.

Subtasks

Subtask #1 (30 points):

  • T≤103T≤103
  • N≤2⋅103N≤2⋅103
  • Sum of NN over all test cases ≤104≤104
  • Time limit: 11 sec

Subtask #2 (70 points):

  • Original Constraints
  • Time limit: 22 sec

Sample Input

2
10    
1 2
1 3
2 4
2 5
3 6
3 7
5 8
6 9   
6 10
7
1 2
2 3
2 4
4 5
4 6
5 7

Sample Output

3 3
8 9 10
1 3
7

Explanation

Test Case 1 :

The assassins are initially present at nodes 44, 77, 88, 99, and 1010 (consider it day 00). On day 11, their positions become:

  • Assassin 44 => Node 22
  • Assassin 77 => Node 33
  • Assassin 88 => Node 55
  • Assassin 99 => Node 66
  • Assassin 1010 => Node 66

Now, since Assassin 44 is in the same path as assassin 88, and assassin 77 is in the same path as assassin 99 and assassin 1010, they both will be assassinated and assassin 88 will get to reach node 22 at cost of 11 day (no benefit) and assassin 99 and 1010 will also reach node 33 in one day (which is Day 22). Now assassin 88 is on node 22 and assassin 99 and 1010 are at node 33, all three of them reach node 11 simultaneously so all three of assassin 88, assassin 99 and assassin 1010 win (With a total cost of 33 days).

Test Case 2 :

The assassins are initially present at node 33, 66, and 77 on day 00. On day 11, their position becomes :

  • Assassin 33 => Node 22
  • Assassin 66 => Node 44
  • Assassin 77 => Node 55

Now since Assassin 33 and assassin 66 are on the path of assassin 77, the assassin 77 will kill both of them and will advance to the position of assassin 33, that is node 22 (nearest position to the kingdom), and this will cost him 11 day. On the next day (day 33), he will reach the kingdom and take the reward.

Solution

C++

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<long long> vec[200008],data,leaves,ans;
void dfs1(long long now, long long last)
{
   for(long long i=0; i<vec[now].size(); i++)
    {
        long long root= vec[now][i];
        if(root!=last)
        dfs1(root,now);
    }
    leaves.clear();
    for(long long i=0; i<vec[now].size(); i++)
    {
        long long root= vec[now][i];
        if(root!=last)
            leaves.push_back(data[root]);
    }
    if(leaves.size()>0)
    {
        sort(leaves.begin(),leaves.end());
        long long x=leaves[0],chk=0;
        for(long long i=0; i<leaves.size(); i++)
        {
            if(leaves[i]!= x)
              chk++;
        }
        if(chk==0)
           data[now]+= x+1;
        if(chk!=0)
           data[now]+= x +2;
    }
    else
    data[now]=0;
}
void dfs2(long long node, long long par, long long minh)
{
    for(long long i=0; i<vec[node].size(); i++)
    {
        long long root= vec[node][i];
        minh = min(minh,data[node]);
        if(root!=par)
        {
            if(data[root]>=minh-1)
            {
               dfs2(root,node,minh);
            }
        }
    }
    if(data[node]==0)
    {
       ans.push_back(node);
    }
}
int main()
{
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   long long t = 1; cin >> t;
    while(t--)
    {
        long long N; cin >> N;
        data.assign(N+1,0);
        for(long long i=0;i<N-1; i++)
        {
            int l, r;
            cin >> l >> r;
            vec[l].pb(r), vec[r].pb(l);
        }
        dfs1(1,0);
        int mn=INT_MAX;
        for(long long i = 0; i<vec[1].size(); i++)
        {
            long long root = vec[1][i];
            if(data[root]<mn)
            {
                mn = data[root];
            }
        }
        for(long long i=0; i<vec[1].size(); i++)
        {
            long long root = vec[1][i];
            if(data[root] == mn)
               dfs2(root,1,mn);
        }
        sort(ans.begin(), ans.end());
        cout<<ans.size()<<" "<<mn+1<<endl;
        for (long long i = 0; i <ans.size(); ++i)
            cout<<ans[i]<<" ";
        cout<<endl;
        for (long long i = 1; i <=N; ++i)
        {
            vec[i].clear();
        }
       data.clear();
       ans.clear();
    }
    return 0;
}

Java

import java.util.*;
import java.io.*;

class KKLING{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        int[] from = new int[N-1], to = new int[N-1];
        for(int i = 0; i< N-1; i++){
            from[i] = ni()-1;
            to[i] = ni()-1;
        }
        int[][] tree = make(N, from, to);
        int[] par = new int[N], d = new int[N];
        int[] location = new int[N];//location of ith assassin, or -1 if i is not an assassin, or i is dead
        int[] node = new int[N];//id of assassin on ith node, or -1 if no assassin on ith node
        Arrays.fill(location, -1);
        Arrays.fill(node, -1);
        precalc(tree, par, d, location, 0, -1);
        for(int i = 0; i< N; i++)if(location[i] != -1)node[location[i]] = i;
        

        int[] set = java.util.stream.IntStream.range(0, N).toArray();//Maintaining sets of assassins
        
        PriorityQueue<int[]> q = new PriorityQueue<>((int[] i1, int[] i2) -> {
            if(d[i1[1]] != d[i2[1]])return Integer.compare(d[i1[1]], d[i2[1]]);
            return Integer.compare(i1[1], i2[1]);
        });
        for(int i = 0; i< N; i++)if(location[i] != -1)q.add(new int[]{i, i});
        boolean[] processed = new boolean[N];
        
        int winTime = -1;
        for(int time = 1; time <= N; time++){
            for(int[] pair:q){
                location[pair[0]] = -1;
                node[pair[1]] = -1;
            }
            //Min-heap to fetch assassin with location closest to root
            PriorityQueue<int[]> nq = new PriorityQueue<>((int[] i1, int[] i2) -> {
                if(d[i1[1]] != d[i2[1]])return Integer.compare(d[i1[1]], d[i2[1]]);
                return Integer.compare(i1[1], i2[1]);
            });
            //Moving to next[u], if u is location (par is eqivalent to next array)
            //pair[0] -> assassin ID
            //pair[1] -> location
            for(int[] pair:q)nq.add(new int[]{pair[0], par[pair[1]]});
            q.clear();
            //Merging assassins at same node
            int prevAssassin = -1, prevNode = -2;
            while(!nq.isEmpty()){
                int[] pair = nq.poll();
                if(pair[1] == prevNode){
                    set[find(set, pair[0])] = find(set, prevAssassin);
                }else {
                    prevNode = pair[1];
                    prevAssassin = pair[0];
                    q.add(new int[]{pair[0], pair[1]});
                    location[pair[0]] = pair[1];
                    node[pair[1]] = pair[0];
                }
            }
            //Checking if some assassin is at node 0 (0-based indexing)
            if(node[0] != -1){
                winTime = time;
                break;
            }
            //Processing all nodes having assassins in order of their depths
            while(!q.isEmpty()){
                int[] pair = q.poll();
                if(processed[pair[1]])continue;//this node is already processed
                process(nq, tree, processed, par, location, node, pair[1], par[pair[1]], pair[0]);
            }
            q = nq;
        }
        List<Integer> ans = new ArrayList<>();
        for(int i = 0; i< N; i++)if(find(set, i) == find(set, node[0]))ans.add(1+i);
        pn(ans.size()+" "+winTime);
        for(int x:ans)p(x+" ");pn("");
    }
    //Processing nodes
    boolean process(PriorityQueue<int[]> q, int[][] tree, boolean[] processed, int[] par, int[] location, int[] node, int u, int p, int ancestor) throws Exception{
        boolean contains = false;//Determining if there's any assassin in subtree of node u except at node u
        for(int v:tree[u]){
            if(v == p || processed[v])continue;
            contains |= process(q, tree, processed, par, location, node, v, u, ancestor == -1?node[u]:ancestor);
            processed[v] = true;
        }
        if(contains && node[u] != -1){
            //Subtree of node u contains an assassin, so assassin at current node dies
            location[node[u]] = -1;
            node[u] = -1;
        }
        if(ancestor != -1 && node[u] != -1){
            //Current assassn survived, and there's some ancestor killed on same day
            //or node u itself, if no assassin in subtree of u
            if(ancestor != node[u])par[u] = location[ancestor];
            q.add(new int[]{node[u], u});
        }
        return contains || node[u] != -1;
    }
    void precalc(int[][] tree, int[] par, int[] d, int[] location, int u, int p){
        par[u] = p;
        location[u] = u;
        for(int v:tree[u])if(v != p){
            location[u] = -1;
            d[v] = d[u]+1;
            precalc(tree, par, d, location, v, u);
        }
    }
    int[][] make(int N, int[] from, int[] to){
        int[] cnt = new int[N];
        for(int x:from)cnt[x]++;
        for(int x:to)cnt[x]++;
        int[][] g = new int[N][];
        for(int i = 0; i< N; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< N-1; i++){
            g[from[i]][--cnt[from[i]]] = to[i];
            g[to[i]][--cnt[to[i]]] = from[i];
        }
        return g;
    }
    int find(int[] set, int u){return set[u] == u?u:find(set, set[u]);}
    static void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
//        new KKLING().run();
        new Thread(null, new Runnable() {public void run(){try{new KKLING().run();}catch(Exception e){e.printStackTrace();System.exit(1);}}}, "1", 1 << 28).start();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Python

from collections import defaultdict
import sys
sys.setrecursionlimit(2000000)
dp = []
def dfs_find_time(adj,parent,curr):
    global dp
    flag = 0
    temp = set()
    mini = float("inf")
    for i in adj[curr]:
        if i!=parent:
            flag += 1
            ans = dfs_find_time(adj,curr,i)
            temp.add(ans)
            mini = min(mini,ans)

    if flag == 0:
        dp[curr] = 0
        return dp[curr]
    if len(temp) == 1:
        dp[curr] = temp.pop()+1
    elif curr == 1:
        dp[curr] = mini+1
    else:
        dp[curr] = mini+2
    return dp[curr]
    
answer = []
def dfs_find_assasins(adj,parent,curr,search=-1):
    global answer
    if search==0 and dp[curr] == 0:
        answer.append(curr)
        return
    if parent == 0 or search==dp[curr]:
        search = dp[curr]-1
    for i in adj[curr]:
        if parent==0:
            if dp[i]==search:
                dfs_find_assasins(adj,curr,i,search)
        else:
            if i!=parent and dp[i]>=search:
                dfs_find_assasins(adj,curr,i,search)


t = int(input())
for _ in range(t):
    
    n = int(input())
    dp = [-1]*(n+1)
    answer = []
    adj_list = defaultdict(list)
    for _ in range(n-1):
        u,v = map(int,input().split())
        adj_list[u].append(v)
        adj_list[v].append(u)
    dfs_find_time(adj_list,0,1)
    dfs_find_assasins(adj_list,0,1)
    answer.sort()
    print(len(answer),dp[1])
    print(*answer)

See more posts here

Leave a Comment

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

x