oj.uz

Submission #246382

# Submission time Handle Problem Language Result Execution time Memory
246382 2020-07-09T02:07:12 Z Ort Birmingham (COCI20_birmingham) Java 11
35 / 70
 1000 ms 79708 KB 
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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 18168 KB Output is correct
2 Correct 120 ms 18168 KB Output is correct
3 Correct 110 ms 18396 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 18220 KB Output is correct
2 Correct 117 ms 18176 KB Output is correct
3 Correct 109 ms 18424 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 18308 KB Output is correct
2 Correct 108 ms 18044 KB Output is correct
3 Correct 108 ms 18072 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 18168 KB Output is correct
2 Correct 114 ms 18316 KB Output is correct
3 Correct 111 ms 18296 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 18524 KB Output is correct
2 Correct 110 ms 18200 KB Output is correct
3 Correct 121 ms 18332 KB Output is correct
4 Correct 119 ms 18196 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 18128 KB Output is correct
2 Correct 121 ms 18112 KB Output is correct
3 Correct 110 ms 18164 KB Output is correct
4 Correct 102 ms 18292 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 18344 KB Output is correct
2 Correct 108 ms 18196 KB Output is correct
3 Correct 102 ms 18752 KB Output is correct
4 Correct 112 ms 18080 KB Output is correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1161 ms 69304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1208 ms 79708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 71764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 69660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1254 ms 72072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1213 ms 72212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1018 ms 75844 KB Time limit exceeded
2 Halted 0 ms 0 KB -