Submission #246382

#	Time	Username	Problem	Language	Result	Execution time	Memory
246382		Ort	Birmingham (COCI20_birmingham)	Java	35 / 70	1254 ms	79708 KiB

birmingham

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
       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;
    }

 }

public class birmingham {
	
	public static int maxN = 200005;
	public static ArrayList<Integer>[] Graph = new ArrayList[maxN];
	public static int Dist[] = new int[maxN];
	public static int Ans[] = new int[maxN];
	public static boolean Visited[] = new boolean[maxN];
	
	public static void main(String[] args) {
		
		for(int i = 0; i < maxN; i++) Graph[i] = new ArrayList<Integer>();
		
		MyScanner sc = new MyScanner();
		int n = sc.nextInt();
		int m = sc.nextInt();
		int q = sc.nextInt();
		int k = sc.nextInt();
		
		Queue<Integer> Q = new ArrayDeque<>();
		
		for(int i = 0; i < q; i++) {
			int source = sc.nextInt();
			Q.add(source);
			Visited[source] = true;
		}
		
		for(int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			Graph[a].add(b);
			Graph[b].add(a);
		}
		
		while(!Q.isEmpty()) {
			int curr = Q.poll();
			
			for(int nxt : Graph[curr]) {
				if(Visited[nxt] == true) continue;
				Visited[nxt] = true;
				Dist[nxt] = Dist[curr] + 1;
				Q.add(nxt);
			}
				
		}
		
		int pt = 1;
		int f = 1;
		while (pt < n) {
		    for(int i = pt; i < (pt + f * k); i++)
		    	if(i < n) Ans[i] = f;
		    pt += f * k;
		    f++;
		}
			
		for(int i = 1; i <= n; i++) {
			System.out.print(Ans[Dist[i]]);
			System.out.print(" ");
		}
		
	}

}

Compilation message (stderr)

Note: birmingham.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5