oj.uz

Submission #246381

# Submission time Handle Problem Language Result Execution time Memory
246381 2020-07-09T02:01:02 Z Ort Birmingham (COCI20_birmingham) Java 11
35 / 70
 1000 ms 84396 KB 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 LinkedList<>();
		
		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 18060 KB Output is correct
2 Correct 115 ms 18296 KB Output is correct
3 Correct 110 ms 18452 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 18308 KB Output is correct
2 Correct 108 ms 18324 KB Output is correct
3 Correct 110 ms 18180 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 18208 KB Output is correct
2 Correct 121 ms 18148 KB Output is correct
3 Correct 107 ms 18596 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 18192 KB Output is correct
2 Correct 109 ms 18336 KB Output is correct
3 Correct 120 ms 18144 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 18232 KB Output is correct
2 Correct 112 ms 18328 KB Output is correct
3 Correct 120 ms 18084 KB Output is correct
4 Correct 113 ms 18128 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 18128 KB Output is correct
2 Correct 125 ms 18584 KB Output is correct
3 Correct 110 ms 18040 KB Output is correct
4 Correct 126 ms 18160 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 18440 KB Output is correct
2 Correct 119 ms 17836 KB Output is correct
3 Correct 127 ms 18208 KB Output is correct
4 Correct 115 ms 18296 KB Output is correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 72284 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 1256 ms 83412 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 1348 ms 84396 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 1232 ms 74872 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 1203 ms 74480 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 1066 ms 70588 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 1227 ms 74724 KB Time limit exceeded
2 Halted 0 ms 0 KB -