library/WeightedDoubling.java

• View this file on GitHub
• Last update: 2023-03-25 01:33:47+09:00

Depends on

• library/AbstractGraph.java
• library/FastIO.java

Verified with

• library/WeightedDoubling_test.java

Code

package library;

import java.util.*;
import java.util.function.*;
import library.FastIO;
import library.AbstractGraph;

final class WeightedDoubling {
	private final long id;
	private final LongBinaryOperator f;
	public final int n;
	public final int log;
	public final int next[][];
	public final long val[][];

	private WeightedDoubling(final int n, final long max, final long id, final LongBinaryOperator f) { // O(1)
		FastIO.nonNegativeCheck(n);
		FastIO.nonNegativeCheck(max);
		this.id = id;
		this.f = f;
		this.n = n;
		log = Long.numberOfTrailingZeros(Long.highestOneBit(max)) + 1;
		next = new int[log][n];
		val = new long[log][n];
		Arrays.fill(next[0], -1);
	}
	// O(NlogM)
	public WeightedDoubling(final int n, final long max, final long id, final LongBinaryOperator f, final Collection<WeightedEdge> edges) {
		this(n, max, id, f);
		for(WeightedEdge e : edges) {
			next[0][e.source] = e.target;
			val[0][e.source] = e.cost;
		}
		init();
	}
	private final void init() {
		for(int k = 0; k + 1 < log; k ++) {
			for(int v = 0; v < n; v ++) {
				if(next[k][v] == -1) {
					next[k + 1][v] = -1;
					val[k + 1][v] = id;
				}else {
					next[k + 1][v] = next[k][next[k][v]];
					val[k + 1][v] = f.applyAsLong(val[k][v], val[k][next[k][v]]);
				}
			}
		}
	}

	WeightedEdge cal(int x, final long q) { // O(logQ)
		FastIO.rangeCheck(x, n);
		FastIO.nonNegativeCheck(q);
		WeightedEdge e = new WeightedEdge(x, x, id);
		for(int k = log - 1; k >= 0; k --) {
			if(e.target == -1) { e.cost = id; break; }
			if((q & 1l << k) != 0) {
				e.cost = f.applyAsLong(e.cost, val[k][e.target]);
				e.target = next[k][e.target];
			}
		}
		return e;
	}

	long bisect(int x, long q) { // O(logM)
		FastIO.rangeCheck(x, n);
		long ans = 0;
		WeightedEdge e = new WeightedEdge(x, x, id);
		for(int k = log - 1; k >= 0; k --) {
			if(e.target == -1) return -1;
			long tmp = f.applyAsLong(e.cost, val[k][e.target]);
			if(tmp <= q) {
				e.cost = tmp;
				e.target = next[k][e.target];
				ans |= 1l << k;
			}
		}
		return ans;
	}
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/user_defined.py", line 71, in bundle
    return subprocess.check_output(shlex.split(command))
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 466, in check_output
    return run(*popenargs, stdout=PIPE, timeout=timeout, check=True,
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.2/x64/lib/python3.11/subprocess.py", line 571, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['false']' returned non-zero exit status 1.

Back to top page