Priya and Parity Solutions CENS20E

Priya and Parity Solutions

There are N urban areas number from 1 to N every city is having a load of wi and they are associated through M bidirectional streets between them. Leave the equality of a city ci alone regardless of whether the quantity of set pieces in its paired portrayal of wi is even and odd something else. 

You are given Q inquiries, each question can be of two kinds: 

1 K – print the size of biggest associated gathering of urban areas in which equality of every city is odd after XOR with K. 

2 K – print the size of biggest associated gathering of urban areas in which equality of every city is even after XOR with K. 

A gathering of urban communities is supposed to be associated on the off chance that we can go from one city of the gathering to some other city of the gathering without going through any city that isn’t in the gathering. A gathering with one city is considered as associated. 

 

Info: 

The main line of the info contains a solitary number T signifying the quantity of experiments. The depiction of T experiments follows. 

The main line contribution of each experiment contains two space-isolated whole numbers N and M. 

The subsequent line contains N space-isolated numbers meaning wi. 

The following M lines contain two space-isolated numbers Ui and Vi, each meaning a bidirectional edge between the urban areas Ui and Vi. 

The following Q lines depict each question in the organization given previously. 

 

Yield: 

For each question of type 1 – print the size of biggest associated gathering of urban communities in which equality of every city is odd after XOR with K. 

For each inquiry of type 2-print the size of biggest associated gathering of urban communities in which equality of every city is even after XOR with K. 

 

Limitations 

1≤T≤5 

1≤N≤2×105 

1≤M≤min(2×105,N×(N−1)2) 

1≤wi,K≤109 

1≤Ui,Vi≤N for each substantial I 

1≤Q≤105 

the diagram contains no copy edges or self-circles 

 

Test Input: 

6 4 10 7 5 

3 4 

5 1 

5 6 

3 6 

1 4 

5 3 

1 6 

1 8 

1 7 

2 6 

 

Test Output: 

 

Clarification: 

Question 1 – The size of the biggest associated gathering of urban communities in which equality of every city is odd after XOR with 6 is equivalent to 1. Since the equality of the city, 2 and 4 is odd after XOR with 6, however 2 isn’t associated with 4. Accordingly the appropriate response is equivalent to 1. 

Question 2 – The size of the biggest associated gathering of urban areas in which equality of every city is odd after XOR with 8 is equivalent to 4 on the grounds that, after XOR with 8, urban communities 2,1,5,3,6 have odd equality. Since 2 isn’t associated with either 1,5,3, or 6, consequently answer is equivalent to 4. 

Also, you can discover the response for different questions.

Solution

import java.util.*;

import java.io.*; 

public class Main{

//Fast IO class

    static class FastReader {

        BufferedReader br; 

        StringTokenizer st; 

        public FastReader() {

        boolean env=System.getProperty(“ONLINE_JUDGE”) != null;

        if(env) {

        try {

br=new BufferedReader(new FileReader(“src\input.txt”));

} catch (FileNotFoundException e) {

e.printStackTrace();

}

        }

        else br = new BufferedReader(new InputStreamReader(System.in)); 

        } 

        String next() {

            while (st == null || !st.hasMoreElements()) {

                try {

                    st = new StringTokenizer(br.readLine()); 

                } 

                catch (IOException  e) {

                    e.printStackTrace(); 

                } 

            } 

            return st.nextToken(); 

        } 

        int nextInt() {

            return Integer.parseInt(next()); 

        } 

        long nextLong() {

            return Long.parseLong(next()); 

        } 

        double nextDouble() {

            return Double.parseDouble(next()); 

        } 

        String nextLine() {

            String str = “”; 

            try {

                str = br.readLine(); 

            } 

            catch (IOException e) {

                e.printStackTrace(); 

            } 

            return str; 

        } 

    }     

    static long MOD=1000000000+7;

    //debug

    static void debug(Object… o) {

        System.out.println(Arrays.deepToString(o));

    }

    // Pair

    static class pair{

    long x,y;

    pair(long a,long b){

    this.x=a;

    this.y=b;

    }

    public boolean equals(Object obj) {

    if(obj == null || obj.getClass()!= this.getClass()) return false;

            pair p = (pair) obj;

            return (this.x==p.x && this.y==p.y);

        }

    public int hashCode() {

            return Objects.hash(x,y);

        }

    }

    static FastReader sc=new FastReader();

    static PrintWriter out=new PrintWriter(System.out);  

    //Global variables and functions

    static int parent[];

    static void init(int n){

    parent=new int[n];

        for(int i=0;i<n;i++) parent[i]=-1;

    }  

    static int find(int n){

        if(parent[n]<0) return n;

        else parent[n]=find(parent[n]);

        return parent[n];

    }

    static void union(int a,int b){

        a=find(a);

        b=find(b);

        if(a!=b) {

        parent[b]+=parent[a];

        parent[a]=b;

        }

    }

    //Main function(The main code starts from here)

    public static void main (String[] args) throws java.lang.Exception {

    int test=1;

    test=sc.nextInt();

    while(test–>0) {

    int n=sc.nextInt(),m=sc.nextInt();

    int a[]=new int[n];

    init(n);

    HashSet<Integer> even=new HashSet<>(),odd=new HashSet<>();

    for(int i=0;i<n;i++) {

    a[i]=sc.nextInt();

    if(Integer.bitCount(a[i])%2==0) even.add(i);

    else odd.add(i);

    }

    for(int i=0;i<m;i++) {

    int s=sc.nextInt()-1,d=sc.nextInt()-1;

    if(even.contains(s) && even.contains(d)) union(s,d);

    if(odd.contains(s) && odd.contains(d)) union(s,d);

    }

    ArrayList<Integer> e=new ArrayList<>(),o=new ArrayList<>();

    int m1=0,m2=0;

    for(Integer x: even) {

    m1=Math.max(m1, -parent[find(x)]);

    e.add(x);

    }

    for(Integer y: odd) {

    m2=Math.max(m2, -parent[find(y)]);

    o.add(y);

    }

    int q=sc.nextInt();

    while(q–>0) {

    int t=sc.nextInt(),k=sc.nextInt();

    int b=Integer.bitCount(k);

    int x=m1,y=m2;

    if(b%2==0) {

    x=m2;

    y=m1;

    }

    if(t==1) out.println(x);

    else out.println(y);

    }

    }

        out.flush();

        out.close();

    }

}

November Challenge 2020 SOLUTION CodeChef

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

DOWNLOAD THE SOLUTION

Leave a Comment

close
error: Content is protected !!