Submission #4091526


Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		MyInput in = new MyInput(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static long LINF = 1L << 55;
	static long MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		int n, m;
		T[] T;
		long x;
		public void solve(int testNumber, MyInput in, PrintWriter out) {

			n = in.nextInt(); m = in.nextInt();
			x = in.nextLong();
			T = new T[m];
			for (int i = 0; i < m; i++) {
				int u = in.nextInt()-1, v = in.nextInt()-1;
				long w = in.nextLong();
				T[i] = new T(u, v, w);
			}

			Arrays.sort(T);

			TreeMap<Long, Long> map = new TreeMap<>();
			for (int i = 0; i < m; i++) {
				long cost = kruskal(i);
				map.merge(cost, 1L, Long::sum);
			}

			long less = 0, equal = 0;
			for (long key : map.keySet()) {
				if (key < x) less += map.get(key);
				if (key <= x) equal += map.get(key);
			}

			long ans = (MOD + f(less) - f(equal)) % MOD;
			out.println(ans);

		}

		long f(long cnt) {
			long ret = 0;
			if (cnt == 0) {
				ret = power(2, m, MOD);
			} else {
				ret = power(2, m - cnt + 1, MOD);
			}
			return ret;
		}

		long power(long a, long e, long modP) {
			long ret = 1;
			for (; e > 0; e /= 2) {
				if (e % 2 != 0) {
					ret = (ret * a) % modP;
				}
				a = (a * a) % modP;
			}
			return ret;
		}

		long kruskal(int i) {

			long ret = 0;
			UnionFind uf = new UnionFind(n);
			uf.union(T[i].s, T[i].t);
			ret += T[i].cost;

			for (int j = 0; j < m; j++) {
				if (uf.same(T[j].s, T[j].t)) continue;
				uf.union(T[j].s, T[j].t);
				ret += T[j].cost;
			}

			return ret;
		}

		class UnionFind {
			int[] data;

			public UnionFind(int size) {
				data = new int[size];
				clear();
			}

			public void clear() {
				Arrays.fill(data, -1);
			}

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

			public void union(int x, int y) {
				x = root(x);
				y = root(y);

				if (x != y) {
					if (data[y] > data[x]) {
						final int t = x;
						x = y;
						y = t;
					}

					data[x] += data[y];
					data[y] = x;
				}
			}

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

			public int size(int x) {
				return -data[root(x)];
			}
		}

		class T implements Comparable<T> {
			int s, t;
			long cost;

			public T(int s, int t, long cost) {
				super();
				this.s = s;
				this.t = t;
				this.cost = cost;
			}

			@Override
			public int compareTo(T o) {
				return Long.compare(this.cost, o.cost);
			}
		}
	}

	static class MyInput {
		private final BufferedReader in;
		private static int pos;
		private static int readLen;
		private static final char[] buffer = new char[1024 * 8];
		private static char[] str = new char[500 * 8 * 2];
		private static boolean[] isDigit = new boolean[256];
		private static boolean[] isSpace = new boolean[256];
		private static boolean[] isLineSep = new boolean[256];

		static {
			for (int i = 0; i < 10; i++) {
				isDigit['0' + i] = true;
			}
			isDigit['-'] = true;
			isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
			isLineSep['\r'] = isLineSep['\n'] = true;
		}

		public MyInput(InputStream is) {
			in = new BufferedReader(new InputStreamReader(is));
		}

		public int read() {
			if (pos >= readLen) {
				pos = 0;
				try {
					readLen = in.read(buffer);
				} catch (IOException e) {
					throw new RuntimeException();
				}
				if (readLen <= 0) {
					throw new MyInput.EndOfFileRuntimeException();
				}
			}
			return buffer[pos++];
		}

		public int nextInt() {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			int i = 0;
			int ret = 0;
			if (str[0] == '-') {
				i = 1;
			}
			for (; i < len; i++)
				ret = ret * 10 + str[i] - '0';
			if (str[0] == '-') {
				ret = -ret;
			}
			return ret;
		}

		public long nextLong() {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			int i = 0;
			long ret = 0;
			if (str[0] == '-') {
				i = 1;
			}
			for (; i < len; i++)
				ret = ret * 10 + str[i] - '0';
			if (str[0] == '-') {
				ret = -ret;
			}
			return ret;
		}

		public char nextChar() {
			while (true) {
				final int c = read();
				if (!isSpace[c]) {
					return (char) c;
				}
			}
		}

		public String nextString() {
			return new String(nextChars());
		}

		public char[] nextChars() {
			int len = 0;
			str[len++] = nextChar();
			len = reads(len, isSpace);
			return Arrays.copyOf(str, len);
		}

		public char[][] next2DChars(int h, int w) {
			char[][] s = new char[h][w];
			for (int i = 0; i < h; i++) {
				s[i] = nextChars();
			}
			return s;
		}

		int reads(int len, boolean[] accept) {
			try {
				while (true) {
					final int c = read();
					if (accept[c]) {
						break;
					}
					if (str.length == len) {
						char[] rep = new char[str.length * 3 / 2];
						System.arraycopy(str, 0, rep, 0, str.length);
						str = rep;
					}
					str[len++] = (char) c;
				}
			} catch (MyInput.EndOfFileRuntimeException e) {
			}
			return len;
		}

		public int[] nextIntArray(final int n) {
			final int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[] nextIntArray1Index(final int n) {
			final int[] res = new int[n + 1];
			for (int i = 1; i < n + 1; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[] nextIntArrayDec(final int n) {
			final int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt() - 1;
			}
			return res;
		}

		public long[] nextLongArray(final int n) {
			final long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long[] nextLongArray1Index(final int n) {
			final long[] res = new long[n + 1];
			for (int i = 1; i < n + 1; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long[] nextLongArrayDec(final int n) {
			final long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong() - 1;
			}
			return res;
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public double[] nextDoubleArray(int n) {
			double[] res = new double[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextDouble();
			}
			return res;
		}

		static class EndOfFileRuntimeException extends RuntimeException {
		}

	}

}

Submission Info

Submission Time
Task E - Bichrome Spanning Tree
User tutuz
Language Java8 (OpenJDK 1.8.0)
Score 900
Code Size 7256 Byte
Status AC
Exec Time 325 ms
Memory 36840 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 4
AC × 52
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01.txt AC 294 ms 34708 KiB
02.txt AC 302 ms 34152 KiB
03.txt AC 300 ms 32204 KiB
04.txt AC 290 ms 31980 KiB
05.txt AC 264 ms 33824 KiB
06.txt AC 288 ms 32876 KiB
07.txt AC 297 ms 32732 KiB
08.txt AC 325 ms 33260 KiB
09.txt AC 292 ms 32108 KiB
10.txt AC 287 ms 32720 KiB
11.txt AC 304 ms 34528 KiB
12.txt AC 236 ms 30924 KiB
13.txt AC 226 ms 28552 KiB
14.txt AC 233 ms 28616 KiB
15.txt AC 320 ms 32728 KiB
16.txt AC 285 ms 32424 KiB
17.txt AC 292 ms 34412 KiB
18.txt AC 292 ms 34284 KiB
19.txt AC 278 ms 32356 KiB
20.txt AC 271 ms 32292 KiB
21.txt AC 292 ms 32236 KiB
22.txt AC 276 ms 36324 KiB
23.txt AC 285 ms 35164 KiB
24.txt AC 239 ms 28264 KiB
25.txt AC 232 ms 28264 KiB
26.txt AC 284 ms 33004 KiB
27.txt AC 308 ms 33128 KiB
28.txt AC 306 ms 32872 KiB
29.txt AC 270 ms 31908 KiB
30.txt AC 297 ms 32552 KiB
31.txt AC 285 ms 32744 KiB
32.txt AC 276 ms 30800 KiB
33.txt AC 294 ms 34796 KiB
34.txt AC 276 ms 32044 KiB
35.txt AC 244 ms 24716 KiB
36.txt AC 235 ms 27096 KiB
37.txt AC 238 ms 26296 KiB
38.txt AC 307 ms 32108 KiB
39.txt AC 298 ms 32960 KiB
40.txt AC 269 ms 32704 KiB
41.txt AC 300 ms 36840 KiB
42.txt AC 243 ms 28152 KiB
43.txt AC 228 ms 27648 KiB
44.txt AC 236 ms 30968 KiB
45.txt AC 229 ms 28992 KiB
46.txt AC 237 ms 31972 KiB
47.txt AC 228 ms 28920 KiB
48.txt AC 228 ms 28048 KiB
sample-01.txt AC 167 ms 24016 KiB
sample-02.txt AC 165 ms 24016 KiB
sample-03.txt AC 158 ms 23632 KiB
sample-04.txt AC 161 ms 23508 KiB