101 lines
2.2 KiB
Java
101 lines
2.2 KiB
Java
package chelper;
|
|
|
|
import static chelper.TaskF.INF;
|
|
|
|
import java.util.HashMap;
|
|
import java.util.Map;
|
|
import java.util.Random;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class TaskFGen extends SimpleSavingChelperSolution {
|
|
|
|
public static final int N = 100000;
|
|
public static final int M = 100020;
|
|
public static final int Q = 100000;
|
|
public static final int MAX_D = 1000000000;
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
boolean input = true;
|
|
|
|
if (input) {
|
|
out.println(N);
|
|
out.println(M);
|
|
}
|
|
|
|
Random random = new Random(0);
|
|
Map<Integer, Map<Integer, Long>> edges = new HashMap<>();
|
|
for (int i = 0; i < N; i++) {
|
|
edges.put(i, new HashMap<>());
|
|
}
|
|
|
|
for (int i = 0; i < N - 1; i++) {
|
|
long c = random.nextInt(MAX_D) + 1;
|
|
edges.get(i).put(i + 1, c);
|
|
edges.get(i + 1).put(i, c);
|
|
if (input) {
|
|
out.println((i + 1) + " " + (i + 2) + " " + c);
|
|
}
|
|
|
|
edges.get(i).put(i, 0L);
|
|
}
|
|
|
|
for (int i = 0; i < M - N + 1; i++) {
|
|
long c = random.nextInt(MAX_D) + 1;
|
|
|
|
int a = random.nextInt(N);
|
|
int b = a;
|
|
|
|
while (b == a || edges.get(a).containsKey(b)) {
|
|
b = random.nextInt(N);
|
|
}
|
|
|
|
edges.get(a).put(b, c);
|
|
edges.get(b).put(a, c);
|
|
if (input) {
|
|
out.println((a + 1) + " " + (b + 1) + " " + c);
|
|
}
|
|
}
|
|
|
|
// for (int k : edges.keySet()) {
|
|
// for (int i : edges.keySet()) {
|
|
// for (int j : edges.keySet()) {
|
|
// edges.get(i).put(j, Math.min(
|
|
// edges.get(i).getOrDefault(j, INF),
|
|
// edges.get(i).getOrDefault(k, INF) + edges.get(k).getOrDefault(j, INF)
|
|
// ));
|
|
// }
|
|
// }
|
|
// }
|
|
|
|
if (input) {
|
|
out.println(Q);
|
|
}
|
|
|
|
for (int i = 0; i < Q; i++) {
|
|
int a = random.nextInt(N);
|
|
int b = a;
|
|
|
|
while (b == a) {
|
|
b = random.nextInt(N);
|
|
}
|
|
if (input) {
|
|
out.println((a + 1) + " " + (b + 1));
|
|
}
|
|
|
|
if (!input) {
|
|
out.println(edges.get(a).get(b));
|
|
}
|
|
}
|
|
|
|
}
|
|
}
|