Submission #1955369


Source Code Expand

package tester;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
	int n;
	long[] x;
	long[] y;
	long[] a;
	double[][] dist;
	double[] weight;
	long[] water;

	class Edge implements Comparable<Edge> {
		int u;
		int v;
		double cost;

		public Edge(int u_, int v_, double dist) {
			u = u_;
			v = v_;
			cost = dist;
		}

		@Override
		public int compareTo(Edge o) {
			return Double.compare(cost, o.cost);
		}
	}

	class UnionFind {
		int n;
		int[] upper;

		public UnionFind(int n_) {
			n = n_;
			upper = new int[n];
			Arrays.fill(upper, -1);
		}

		int root(int x) {
			return upper[x] < 0 ? x : (upper[x] = root(upper[x]));
		}

		boolean equiv(int x, int y) {
			return root(x) == root(y);
		}

		void setUnion(int x, int y) {
			x = root(x);
			y = root(y);
			if (x == y)
				return;
			if (upper[x] < upper[y]) {
				x ^= y;
				y ^= x;
				x ^= y;
			}
			upper[y] += upper[x];
			upper[x] = y;
		}
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		x = new long[n];
		y = new long[n];
		a = new long[n];
		dist = new double[n][n];
		weight = new double[1 << n];
		water = new long[1 << n];
		for (int i = 0; i < n; ++i) {
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			a[i] = sc.nextInt();
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (i == j)
					continue;
				dist[i][j] = Math.sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
			}
		}
		for (int s = 1; s < 1 << n; ++s) {
			UnionFind uf = new UnionFind(n);
			PriorityQueue<Edge> pq = new PriorityQueue<>();
			for (int i = 0; i < n; ++i) {
				if ((s >> i) % 2 == 0)
					continue;
				water[s] += a[i];
				for (int j = i + 1; j < n; ++j) {
					if ((s >> j) % 2 == 0)
						continue;
					pq.add(new Edge(i, j, dist[i][j]));
				}
			}
			while (!pq.isEmpty()) {
				Edge e = pq.poll();
				if (uf.equiv(e.u, e.v))
					continue;
				weight[s] += e.cost;
				uf.setUnion(e.u, e.v);
			}
		}
		double[] a = new double[1 << n];
		a[0] = 1 << 30;
		for (int s = 0; s < 1 << n; ++s) {
			for (int s2 = ((1 << n) - 1) & ~s; s2 > 0; s2 = (s2 - 1) & ~s) {
				int m = Integer.bitCount(s2);
				int ns = s | s2;
				a[ns] = Math.max(a[ns], Math.min(a[s], ((water[s2] - weight[s2]) / m)));
			}
		}
		System.out.printf("%.20f", a[(1 << n) - 1]);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Submission Info

Submission Time
Task E - Water Distribution
User fortoobye
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 2623 Byte
Status RE
Exec Time 80 ms
Memory 24916 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
RE × 2
RE × 46
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt RE 80 ms 18004 KB
001.txt RE 77 ms 19924 KB
002.txt RE 78 ms 17876 KB
003.txt RE 80 ms 21332 KB
004.txt RE 77 ms 20692 KB
005.txt RE 78 ms 18388 KB
006.txt RE 77 ms 21460 KB
007.txt RE 77 ms 19540 KB
008.txt RE 79 ms 21204 KB
009.txt RE 78 ms 18900 KB
010.txt RE 78 ms 19540 KB
011.txt RE 76 ms 18388 KB
012.txt RE 79 ms 20692 KB
013.txt RE 77 ms 18644 KB
014.txt RE 79 ms 20436 KB
015.txt RE 79 ms 20052 KB
016.txt RE 78 ms 20948 KB
017.txt RE 79 ms 21460 KB
018.txt RE 79 ms 20564 KB
019.txt RE 79 ms 20564 KB
020.txt RE 79 ms 21460 KB
021.txt RE 78 ms 22100 KB
022.txt RE 78 ms 20948 KB
023.txt RE 79 ms 18388 KB
024.txt RE 79 ms 18388 KB
025.txt RE 77 ms 19412 KB
026.txt RE 80 ms 21204 KB
027.txt RE 80 ms 17620 KB
028.txt RE 78 ms 18132 KB
029.txt RE 77 ms 20948 KB
030.txt RE 79 ms 21204 KB
031.txt RE 77 ms 19796 KB
032.txt RE 77 ms 19796 KB
033.txt RE 79 ms 20820 KB
034.txt RE 78 ms 19156 KB
035.txt RE 77 ms 19540 KB
036.txt RE 78 ms 19412 KB
037.txt RE 77 ms 21332 KB
038.txt RE 76 ms 21204 KB
039.txt RE 79 ms 24916 KB
040.txt RE 76 ms 18516 KB
041.txt RE 78 ms 18644 KB
042.txt RE 78 ms 19924 KB
043.txt RE 78 ms 19284 KB
example0.txt RE 77 ms 20180 KB
example1.txt RE 76 ms 18004 KB