Even edges (getting tle in one case of 2nd subtask)

1

import java.util.;
import java.lang.;
import java.io.*;
public class Main
{
public static void main(String[] args) throws java.lang.Exception {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int t= Integer.parseInt(st.nextToken());
while(t–!=0){
st = new StringTokenizer(br.readLine());
int n= Integer.parseInt(st.nextToken());
int m= Integer.parseInt(st.nextToken());

	    ArrayList<ArrayList<Integer>> arr= new ArrayList<>();
	    
	    for(int i=0;i<n;i++){
	        ArrayList<Integer> a= new ArrayList<Integer>();
	        arr.add(a);
	    }
	    int odd=-1;
	    int a=0,b=0;
	    for(int i=0;i<m;i++){
	        st = new StringTokenizer(br.readLine());
	        a= Integer.parseInt(st.nextToken());
	        b= Integer.parseInt(st.nextToken());
	        arr.get(a-1).add(b-1);
	        arr.get(b-1).add(a-1);
	    }
	    // even edges
	    if(m%2==0){
	        System.out.println(1);
	        for(int i=0;i<n;i++){
	            System.out.print(1+" ");
	        }
	        System.out.println();
	        continue;
	    }
	    
	    // odd edges
	    int odd=-1;
	    for(int i=0;i<n;i++){
	        if(arr.get(i).size()%2==1){
	            odd=i;
	            break;
	        }
	    }
	    
	        if(odd!=-1){
	            System.out.println(2);
	          for(int j=0;j<n;j++){
	            if(j==odd){
                      System.out.print(1+" ");
	               }
	          else{
	                        System.out.print(2+" ");
	                    }
	               }
                   System.out.println();	                
	                
	            
	        }
	        else{
	            System.out.println(3);
	            for(int i=0;i<n;i++){
	                if(i==a-1){
	                    System.out.print(1+" ");
	                }
	                else if(i==b-1){
	                    System.out.print(2+" ");
	                }
	                else{
	                    System.out.print(3+" ");
	                }
	            }
	            System.out.println();
	        }
	    
	}
	br.close();
}

}

2

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

1 Like
3

CodeChef: Practical coding for everyone here is the link

4

Hmm … not much going on, there - could be that you are reading in input in a way that is really slow in Java.

I’d recommend looking at AC Java submissions (why oh why are < 100pt solutions lumped in with 100pt solutions??) and see how they are handling input.

2 Likes
5

With Java I use:

class FastReader {
BufferedReader br;
StringTokenizer st;

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

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

public char nextChar() {
    return next().charAt(0);
}

public int nextInt() {
    return Integer.parseInt(next());
}

public long nextLong() {
    return Long.parseLong(next());
}

public double nextDouble() {
    return Double.parseDouble(next());
}

public String nextLine() {
    String str = "";
    try {
        str = br.readLine();
    } catch (IOException e) {
        e.printStackTrace();
    }
    return str;
}

public int[] nextIntArray(int n) {
    int[] a = new int[n];
    for(int i = 0; i < n; i ++)
        a[i] = nextInt();
    return a;
}

public Integer[] nextIntegerArray(int n) {
    Integer[] a = new Integer[n];
    for(int i = 0; i < n; i ++)
        a[i] = nextInt();
    return a;
}

public long[] nextLongArray(int n) {
    long[] a = new long[n];
    for(int i = 0; i < n; i ++)
        a[i] = nextLong();
    return a;
}

public double[] nextDoubleArray(int n) {
    double[] a = new double[n];
    for(int i = 0; i < n; i ++)
        a[i] = nextDouble();
    return a;
}

public String[] nextStringArray(int n) {
    String[] a = new String[n];
    for(int i = 0; i < n; i ++)
        a[i] = next();
    return a;
}

}

for reading

and

BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

for writing.

2 Likes
6

None of the codes (AC) used 2d arraylist. By using a single 1d array, I’m getting an AC too. The logic remains same more or less. Thanks anyways.
Link to accepted code: CodeChef: Practical coding for everyone

1 Like