Submission #827096

---

Source Code Expand

import std.algorithm;
import std.range;
import std.stdio;
import std.typecons;

immutable int NA = -1;

void main ()
{
	int n, m;
	while (readf (" %s %s", &n, &m) > 0)
	{
		auto u = new int [m];
		auto v = new int [m];
		foreach (i; 0..m)
		{
			readf (" %s %s", &u[i], &v[i]);
		}
		u[] -= 1;
		v[] -= 1;

		alias Record = Tuple !(int, q{p}, int, q{r}, int, q{t});
		auto a = new Record [] [n];
		foreach (i; 0..n)
		{
			a[i] = [Record (i, 1, 0)];
		}

		int place (int w, int t)
		{
			int lo = 0;
			int hi = cast (int) (a[w].length) - 1;
			while (lo < hi)
			{
				int me = (lo + hi + 1) >> 1;
				if (a[w][me].t > t)
				{
					hi = me - 1;
				}
				else
				{
					lo = me;
				}
			}
			return lo;
		}

		int root (int w, int t)
		{
			int i = place (w, t);
			while (a[w][i].t > t)
			{
				i -= 1;
			}
			if (w == a[w][i].p)
			{
				return w;
			}
			return root (a[w][i].p, t);
		}

		void unite (int d, int e, int t)
		{
			d = root (d, t);
			e = root (e, t);
			if (d == e)
			{
				return;
			}
			int id = place (d, t);
			int ie = place (e, t);
			if (a[d][id].r < a[e][ie].r)
			{
				swap (d, e);
				swap (id, ie);
			}
			a[d] ~= Record (d, a[d][id].r + a[e][ie].r, t);
			a[e] ~= Record (d, a[e][ie].r, t);
		}

		foreach (int i; 0..m)
		{
			unite (u[i], v[i], i + 1);
		}

		int q;
		readf (" %s", &q);
		auto x = new int [q];
		auto y = new int [q];
		auto z = new int [q];
		foreach (j; 0..q)
		{
			readf (" %s %s %s", &x[j], &y[j], &z[j]);
		}
		x[] -= 1;
		y[] -= 1;

		auto res = new int [q];
		res[] = NA;
		int ilo = 0;
		foreach (j; 0..q)
		{
			int lo = 0;
			int hi = m;
			while (lo < hi)
			{
				int me = (lo + hi) >> 1;
				int cx = root (x[j], me);
				int cy = root (y[j], me);
				int cz = a[cx][place (cx, me)].r;
				if (cy != cx)
				{
					cz += a[cy][place (cy, me)].r;
				}
				if (cz >= z[j])
				{
					hi = me;
				}
				else
				{
					lo = me + 1;
				}
			}
			res[j] = lo;
		}

		writefln ("%(%s\n%)", res);
	}
}

Submission Info

Judge Result