Nearest Meeting Cell
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
// Reading format inferred from the sample:
// T (number of test cases)
// For each test:
// N
// N integers: next[0..N-1] (use -1 for no exit)
// c1 c2
int T = fs.nextInt();
StringBuilder out = new StringBuilder();
while (T-- > 0) {
int N = fs.nextInt();
int[] next = new int[N];
for (int i = 0; i < N; i++) next[i] = fs.nextInt();
int c1 = fs.nextInt();
int c2 = fs.nextInt();
int ans = closestMeetingCell(next, c1, c2);
out.append(ans).append('\n');
}
System.out.print(out.toString());
}
// Core logic
static int closestMeetingCell(int[] next, int c1, int c2) {
int n = next.length;
int[] d1 = walkDistances(next, c1);
int[] d2 = walkDistances(next, c2);
int bestNode = -1;
long best = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (d1[i] >= 0 && d2[i] >= 0) {
long worst = Math.max(d1[i], d2[i]);
if (worst < best || (worst == best && i < bestNode)) {
best = worst;
bestNode = i;
}
}
}
return bestNode;
}
// Record distance from start to each reachable node; -1 means unreachable.
static int[] walkDistances(int[] next, int start) {
int n = next.length;
int[] dist = new int[n];
Arrays.fill(dist, -1);
int cur = start, d = 0;
while (cur != -1 && dist[cur] == -1) {
dist[cur] = d++;
cur = next[cur];
}
return dist;
}
// Lightweight fast scanner for Java 8
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { this.in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, val = 0;
do { c = read(); } while (c <= ' '); // skip spaces
if (c == '-') { sgn = -1; c = read(); }
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sgn;
}
}
}
Largest Sum Cycle
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
// Input format, inferred to match your screenshots:
// T
// For each test case:
// N
// N integers next[0..N-1] (use -1 for no exit; if your data uses some other senti
int T = fs.nextInt();
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
int N = fs.nextInt();
int[] next = new int[N];
for (int i = 0; i < N; i++) next[i] = fs.nextInt();
long ans = largestSumCycle(next);
sb.append(ans).append('\n');
}
System.out.print(sb.toString());
}
// Core: Find maximum sum of node indices in any cycle; -1 if none.
static long largestSumCycle(int[] next) {
int n = next.length;
byte[] state = new byte[n]; // 0 = unvisited, 1 = in path, 2 = processed
int[] seenAt = new int[n];
long[] prefAt = new long[n];
int tick = 1;
long best = -1;
for (int start = 0; start < n; start++) {
if (state[start] != 0) continue;
int u = start;
while (u != -1 && state[u] == 0) {
state[u] = 1;
seenAt[u] = tick++;
u = next[u];
}
if (u != -1 && state[u] == 1) {
long sum = 0;
int cur = u;
do {
sum += cur;
cur = next[cur];
} while (cur != u && cur != -1);
best = Math.max(best, sum);
}
int x = start;
while (x != -1 && state[x] == 1) {
state[x] = 2;
x = next[x];
}
}
return best;
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, val = 0;
do { c = read(); } while (c <= ' ');
if (c == '-') { sgn = -1; c = read(); }
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sgn;
}
}
}
Maximum Weight Node
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
// Expected input format:
// T
// For each test:
// N
// N integers: next[0..N-1] (use -1 for no exit)
int T = fs.nextInt();
StringBuilder out = new StringBuilder();
while (T-- > 0) {
int N = fs.nextInt();
int[] next = new int[N];
for (int i = 0; i < N; i++) next[i] = fs.nextInt();
int ans = maximumWeightNode(next);
out.append(ans).append('\n');
}
System.out.print(out.toString());
}
static int maximumWeightNode(int[] next) {
int n = next.length;
long[] w = new long[n];
boolean anyIncoming = false;
for (int i = 0; i < n; i++) {
int v = next[i];
if (v >= 0 && v < n) {
w[v] += i;
anyIncoming = true;
}
}
if (!anyIncoming) return -1;
long bestW = Long.MIN_VALUE;
int bestIdx = -1;
for (int v = 0; v < n; v++) {
if (w[v] > bestW || (w[v] == bestW && v > bestIdx)) {
bestW = w[v];
bestIdx = v;
}
}
return bestIdx;
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, val = 0;
do { c = read(); } while (c <= ' ');
if (c == '-') { sgn = -1; c = read(); }
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sgn;
}
}
}
