Submission #697856

#	Time	Username	Problem	Language	Result	Execution time	Memory
697856		vjudge1	Evacuation plan (IZhO18_plan)	Java	0 / 100	4062 ms	79348 KiB

plan

import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.IntStream;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.stream.IntStream.*;

/********************************************/
public class plan {
	public static void main(String[] args) throws IOException {
		new Solution().run();
	}
}
/********************************************/

class Solution {
	final FastScanner scanner = new FastScanner();
	final PrintWriter out = new PrintWriter(System.out);
	final int mod = (int) 1e9+7;
	final int[] dx = {1, 0, -1, 0};
	final int[] dy = {0, 1, 0, -1};
	int maxn = (int) 3e5+10;
	int[] npp, d, p, size;
	List<Pair<Integer, Pair<Integer, Integer>>> e = new ArrayList<>();
	HashSet<Integer>[] set;

	void solve() throws IOException {
		int n = scanner.nextInt(), m = scanner.nextInt();
		init(n); d = new int[n+1]; 
		fill(d, mod);
		p = new int[n+1]; size = new int[n+1];
		for (int i = 0; i<=n; i++) {
			p[i] = i;
			size[i] = 1;
		}
		for (int i = 0; i<m; i++) {
			int x = scanner.nextInt(), y = scanner.nextInt(), w = scanner.nextInt();
			g[x].add(new Pair(y, w));
			g[y].add(new Pair(x, w));
		}
		PriorityQueue<Pair<Integer, Integer>> q = new PriorityQueue<>(Comparator.comparingInt((p) -> p.first));
		int k = scanner.nextInt();
		npp = new int[k];
		for (int i = 0; i<k; i++) {
			npp[i] = scanner.nextInt();
			d[npp[i]] = 0;
			q.add(mp(-d[npp[i]], npp[i]));
		}
		while (!q.isEmpty()) {
			var curr = q.poll();
			int dist = curr.first, v = curr.second;
			if (dist>d[v]) continue;
			for (var node : g[v]) {
				int to = node.first, cost = node.second;
				if (d[to]>d[v]+cost) {
						d[to] = d[v]+cost;
						q.add(mp(-d[to], to));
				}
			}
		}
		int Q = scanner.nextInt();
		var ans = new int[Q];
		for (int i = 1; i<=Q; i++) {
			int x = scanner.nextInt(), y = scanner.nextInt();
			set[x].add(i-1);
			set[y].add(i-1);
		}
		for (int i = 1; i<=n; i++) {
			for (var node : g[i]) {
				e.add(new Pair(min(d[i], d[node.first]), mp(i, node.first)));
			}
		}
		e.sort((x, y)->(x.first-y.first));
		for (int i = e.size()-1; i>=0; i--) {
			int cost = e.get(i).first;
			int a = find(e.get(i).second.first), b = find(e.get(i).second.second);
			if (a == b) continue;
			if (set[a].size()<set[b].size()) {
				int temp = a;
				a = b;
				b = temp;
			}
			for (var ind : set[b]) {
				if (set[a].size()>0) {
					ans[ind] = cost;
					set[a].add(ind);
				} else {
					set[a].add(ind);
				}
			}
			p[b] = a;
		}
		StringBuilder builder = new StringBuilder();
		for (int i : ans)
			 builder.append(i).append(' ');
		out.println(builder);
	}

	int find(int u) {
		if (u == p[u]) return u;
	    return p[u] = find(p[u]);
	}

	void swap(int[] a, int i, int j) {
		int temp = a[i];
	    a[i] = a[j];
	    a[j] = temp;
	}
	
	void swap(long[] a, int i, int j) {
	 	long temp = a[i];
	    a[i] = a[j];
	    a[j] = temp;
	}
	
	void swap(HashMap<Integer, Integer>[] a, int i, int j) {
	 	HashMap<Integer, Integer> temp = a[i];
	    a[i] = a[j];
	    a[j] = temp;
	}

	Pair<Integer, Integer> mp(int x, int y) {
		return new Pair(x, y);
	}

	List<Pair<Integer, Integer>>[] g;
	boolean[] was;

	void init(int n) {
		g = new ArrayList[n+1];
		was = new boolean[n+1];
		set = new HashSet[n+1];
		for (int i = 0; i<=n; i++) {
			g[i] = new ArrayList<>();
			set[i] = new HashSet<>();
		}
	}

	void run() throws IOException {
		int t = 1;
		while (t-->0) {
			solve();
		}
		out.flush();
	}
}

class Pair<First, Second> {
	First first;
	Second second;
	public Pair(First first, Second second) {
		this.first = first;
		this.second = second;
	} 
}

class FastScanner {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	int nextInt() throws IOException {
		int x = 0, sign = 1;
		char c = (char) br.read();
		
		while ((c < '0' || c > '9') && c != '-') {
			c = (char) br.read();
		}
		if (c == '-') {
			sign = -1;
			c = (char) br.read();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 3) + (x << 1) + (c & 15);
			c = (char) br.read();
		}
		return sign * x;
	}
	
	long nextLong() throws IOException {
		long x = 0, sign = 1;
		char c = (char) br.read();
		
		while ((c < '0' || c > '9') && c != '-') {
			c = (char) br.read();
		}
		if (c == '-') {
			sign = -1;
			c = (char) br.read();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 3) + (x << 1) + (c & 15);
			c = (char) br.read();
		}
		return sign * x;
	}
	
	String next() throws IOException {
		StringBuilder sb = new StringBuilder();
		char c = (char) br.read();
		while (c == ' ' || c == '\n' || c == '\r') {
			c = (char) br.read();
		}
		while (c != ' ' && c != '\n' && c != '\r') {
			sb.append(c);
			c = (char) br.read();
		}
		return sb.toString();
	}
	
	int[] readArray(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) a[i] = nextInt();
		return a;
	}
	
	long[] readLong(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++) a[i] = nextInt();
		return a;
	}
}

Compilation message (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46