Submission #729328

#	Time	Username	Problem	Language	Result	Execution time	Memory
729328		CutSandstone	Mecho (IOI09_mecho)	Java	21 / 100	588 ms	65536 KiB

mecho

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class mecho {
	// change to ur file
	private static final String localTestInputFile = "C:\\Users\\anaba\\eclipse-workspace\\test\\src\\main\\java\\input.in";
	private static final String localTestOutputFile = "C:\\Users\\anaba\\eclipse-workspace\\test\\src\\main\\java\\input.out";
	// for usaco only
	private static final String name = "cowjog";
	// constants to use
	private static final int mod = 1_000_000_007, mm = 998244353, inf = Integer.MAX_VALUE;
	private static final int[][] d4 = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	private static final long inf2 = Long.MAX_VALUE;
	// all are primes
	private static final long mod1 = 4611686018427387847L, mod2 = 4611686018427387833L, mod3 = 4611686018427387813L;
	// need to generate Mod.fast(int max) first to use
	private static long[] fact;
	private static PrintWriter out;
	private static FastIO sc;
	private static long time = -1;
	public static void main(String[] args) throws Exception {
		// super giga brain reader that accounts for all platforms and displays time when its ur own platform
		try {
			if(name.length() != 0 && new File(name+".in").exists()) {
				sc = new FastIO(name+".in");
				out = new PrintWriter(name+".out");
			}else if(new File(localTestInputFile).exists()){
				sc = new FastIO(localTestInputFile);
				out = new PrintWriter(new BufferedOutputStream(System.out));
				time = System.currentTimeMillis();
			}else {
				sc = new FastIO(System.in);
				out = new PrintWriter(new BufferedOutputStream(System.out));
			}
		}catch(SecurityException e) {
			sc = new FastIO(System.in);
			out = new PrintWriter(new BufferedOutputStream(System.out));
		}
//		for(int T = sc.nextInt(); T>0; T--) 
			solve();
		if(time != -1) System.out.println("Time: "+(System.currentTimeMillis()-time)+"ms");
        out.close();
	}
	private static void solve() throws Exception {
		int N = sc.nextInt(), S = sc.nextInt();
		LinkedList<int[]> hive = new LinkedList<>();
		final int[] st = new int[2], en = new int[2];
		final boolean[][] go = new boolean[N][N];
		final int[][] bees = new int[N][N];
		for(int[] a: bees) Arrays.fill(a, inf);
		for(int i = 0; i<N; i++) {
			char[] c = sc.chars();
			for(int j = 0; j<N; j++) {
				go[i][j] = c[j] != 'T';
				if(c[j] == 'M') {
					st[0] = i;
					st[1] = j;
				}
				if(c[j] == 'D') {
					en[0] = i;
					en[1] = j;
				}
				if(c[j] == 'H') {
					hive.add(new int[] {i, j});
					bees[i][j] = 0;
				}
			}
		}
		while(!hive.isEmpty()) {
			int[] curr = hive.poll();
			int c = bees[curr[0]][curr[1]];
			for(int[] a: d4) {
				int[] next = new int[] {curr[0]+a[0], curr[1]+a[1]};
				if(next[0] >= 0 && next[1] >= 0 && next[0] < N && next[1] < N && 
				go[next[0]][next[1]] && bees[next[0]][next[1]] == inf && !Arrays.equals(next, en)) {
					bees[next[0]][next[1]] = c+1;
					hive.add(next);
				}
			}
		}
		out.println(BS.last(0, bees[st[0]][st[1]], (t) -> {
			LinkedList<int[]> bfs = new LinkedList<>();
			bfs.add(new int[] {st[0], st[1], 0});
			while(!bfs.isEmpty()) {
				int[] curr = bfs.poll();
				for(int[] a: d4) {
					int[] next = new int[] {curr[0]+a[0], curr[1]+a[1], curr[2]+1};
					if(next[0] >= 0 && next[0] < N && next[1] >= 0 && next[1] < N && 
					go[next[0]][next[1]] && next[2]/S < bees[next[0]][next[1]]-t) {
						if(next[0] == en[0] && next[1] == en[1]) return true;
						bfs.add(next);
					}
				}
			}
			return false;
		}));
    }
    // Mo's algorithm
    private static class MoAlg<T, Edit> {
    	public interface Add<Edit, T> {public void add(Edit a, T curr, boolean first);}
    	public interface Rem<Edit, T> {public void rem(Edit a, T curr, boolean first);}
    	public interface Get<Edit> {public Object get(Edit a);}
    	private final T[] nums;
    	private final int block;
    	private final List<int[]> quer;
    	private final Add<Edit, T> add;
    	private final Rem<Edit, T> rem;
    	private final Get<Edit> get;
    	private Edit def;
    	public MoAlg(T[] nums, Add<Edit, T> add, Rem<Edit, T> rem, Get<Edit> get, Edit def) {
    		this.add = add;
    		this.rem = rem;
    		this.get = get;
    		this.nums = nums;
    		this.def = def;
    		block = (int)Math.sqrt(nums.length);
    		quer = new ArrayList<>();
    	}
		public void add(int l, int r) {
    		quer.add(new int[] {l, r, quer.size()});
    	}
    	public Object[] getAns() {
    		Collections.sort(quer, (a, b) -> a[0]/block == b[0]/block ? ((((a[0]/block)&1) == 0) ? a[1]-b[1]:b[1]-a[1]):a[0]-b[0]);
    		int l = 0, r = -1;
    		Object[] ans = new Object[quer.size()];
    		for(int[] a: quer) {
    			if(r < a[0] || l > a[1]) {
    				for(int i = l; i<=r; i++) rem.rem(def, nums[i], true);
    				for(int i = a[0]; i<=a[1]; i++) add.add(def, nums[i], false);
    			}else {
    				if(l > a[0]) for(int i = l-1; i>=a[0]; i--) add.add(def, nums[i], true);
    				else for(int i = l; i<a[0]; i++) rem.rem(def, nums[i], true);
    				if(r > a[1]) for(int i = r; i>a[1]; i--) rem.rem(def, nums[i], false);
    				else for(int i = r+1; i<=a[1]; i++) add.add(def, nums[i], false);
    			}
    			l = a[0];
    			r = a[1];
    			ans[a[2]] = get.get(def);
    		}
    		return ans;
    	}
    }
    // combiners used for later
    public interface Comb<Val>{Val oper(Val left, Val right);}
	public interface Prop<Val, Lz> {Val oper(Lz top, Val current, long len);}
	public interface LZ<Lz>{Lz oper(Lz top, Lz current);}
	public interface Def<Val>{Val get(long len);}
	public interface DefLz<Lz>{Lz get();}
	// convex hull trick
    private static class CHT {
	    private List<Line> lines;
	    private boolean max;
	    
	    public CHT(boolean max) {
	        this.lines = new ArrayList<>();
	        this.max = max;
	    }
	    public boolean isEmpty() {return lines.isEmpty();}
	    public void add(long m, long b) {
	    	if(max) {
	    		m*=-1;
	    		b*=-1;
	    	}
	        Line line = new Line(m, b);
	        while (lines.size() >= 2) {
	            Line l1 = lines.get(lines.size() - 1);
	            Line l2 = lines.get(lines.size() - 2);
	            if (BigInteger.valueOf(l1.b-l2.b).multiply(BigInteger.valueOf(l1.m-line.m))
	            		.compareTo(BigInteger.valueOf(line.b-l1.b).multiply(BigInteger.valueOf(l2.m-l1.m))) == 1)
	                lines.remove(lines.size() - 1);
	            else break;
	        }
	        lines.add(line);
	    }
 
	    public long get(long x) {
	        int lo = 0, hi = lines.size() - 1;
	        while (lo < hi) {
	            int mid = (lo + hi) / 2;
	            if (lines.get(mid).yValue(x) < lines.get(mid + 1).yValue(x))
	                hi = mid;
	            else lo = mid + 1;
	        }
	        return (max ? -1:1)*lines.get(lo).yValue(x);
	    }
 
	    private static class Line {
	        private long m;
	        private long b;
 
	        public Line(long m, long b) {
	            this.m = m;
	            this.b = b;
	        }
 
	        public long yValue(long x) {
	            return m * x + b;
	        }
	    }
	}
    // convex hull
    private static int[][] hull(int[][] points) {
        Arrays.sort(points, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
        int n = points.length;
        boolean[] used = new boolean[n];
        int[] hull = new int[n + 2];
        int top = 0;
        for (int i = 0; i < n; i++) {
            while (top >= 2 && area(points[hull[top - 1]], points[hull[top]], points[i]) > 0) {
                used[hull[top--]] = false;
            }
            hull[++top] = i;
            used[i] = true;
        }

        used[0] = false;
        for (int i = n - 1; i >= 0; i--) {
            if (used[i]) continue;
            while (top >= 2 && area(points[hull[top - 1]], points[hull[top]], points[i]) > 0) {
                top--;
            }
            hull[++top] = i;
        }
        top--;
        int[][] res = new int[top][2];
        for (int i = 1; i <= top; i++) res[i - 1] = points[hull[i]];
        return res;
    }private static int area(int[] a, int[] b, int[] c) {
        return cross(b[0] - a[0], b[1] - a[1], c[0] - a[0], c[1] - a[1]);
    }private static int cross(int x1, int y1, int x2, int y2) {
        return x1 * y2 - x2 * y1;
    }
    // dijkstra's
	private static long[] minPath(int x, List<int[]>[] g) {
		long[] l = new long[g.length];
		PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Long.compare(l[a], l[b]));
		Arrays.fill(l, Long.MAX_VALUE);
		l[x] = 0;
		pq.add(x);
		while (!pq.isEmpty()) {
			int c = pq.poll();
			for (int[] a : g[c])
				if (l[a[0]] > l[c] + a[1]) {
					l[a[0]] = l[c] + a[1];
					pq.add(a[0]);
				}
		}
		return l;
	}
	// range add, point query
	private static class RevBIT {
		private final long[] bit;
		private final long[] arr;
		private final int len;
		
		public RevBIT(int len) {
			bit = new long[len + 1];
			arr = new long[len];
			this.len = len;
		}
		
		public void set(int ind, long val) {
			add(ind, ind, val - get(ind));
		}
		
		public void add(int s, int e, long val) {
			add(s, val);
			if (e != len - 1)
				add(e + 1, -val);
		}
		
		private void add(int ind, long val) {
			arr[ind] += val;
			ind++;
			for (; ind <= len; ind += ind & -ind)
				bit[ind] += val;
		}
		
		public long diff(int ind) {
			return arr[ind];
		}
		
		public long get(int ind) {
			ind++;
			long sum = 0;
			for (; ind > 0; ind -= ind & -ind)
				sum += bit[ind];
			return sum;
		}
		
		@Override
		public String toString() {
			StringBuilder ret = new StringBuilder();
			ret.append("[");
			for (int i = 0; i < len; i++)
				ret.append(get(i) + (i == len - 1 ? "]" : ", "));
			return ret.toString();
		}
	}
	// binary jumping lca
	private static int lca(int a, int b, int[][] jp, int[] depth) {
		if(depth[a] > depth[b]) {
			int s = a;
			a = b;
			b = s;
		}
		b = jump(b, depth[b]-depth[a], jp);
		if(a == b) return a;
		for(int i = jp[0].length-1; i>=0; i--) if(jp[a][i] != jp[b][i]) {
			a = jp[a][i];
			b = jp[b][i];
		}
		return jp[a][0];
	}
	// binary jumping jump
	private static int jump(int a, int k, int[][] jp) {
		for(int i = 0; i<jp[0].length; i++) if((k&(1<<i)) != 0) {
			a = jp[a][i];
			if(a == -1) return -1;
		}
		return a;
	}
	// heavy light decomposition
	private static int[][] HLD(List<Integer>[] g){
		int N = g.length;
		int[] pos = new int[N], last = new int[N], cnt = new int[N];
		dfsCNTHLD(g, cnt, 0, -1);
		dfsHLD(g, pos, last, 0, 0, -1, cnt);
		return new int[][] {pos, last};
	}private static void dfsCNTHLD(List<Integer>[] g, int[] cnt, int s, int p) {
		cnt[s] = 1;
		for(int i: g[s]) if(i != p) {
			dfsCNTHLD(g, cnt, i, s);
			cnt[s]+=cnt[i];
		}
	}private static int dfsHLD(List<Integer>[] g, int[] pos, int[] last, int timer, int s, int p, int[] cnt) {
		pos[s] = timer++;
		int m = -1;
		for(int i: g[s]) if(i != p)
			if(m == -1 || cnt[i] > cnt[m]) m = i;
		if(m == -1) return timer;
		last[m] = last[s];
		timer = dfsHLD(g, pos, last, timer, m, s, cnt);
		for(int i: g[s]) if(i != p && i != m) {
			last[i] = i;
			timer = dfsHLD(g, pos, last, timer, i, s, cnt);
		}
		return timer;
	}
	// strongly connected components
	private static List<List<Integer>> SCC(List<Integer>[] g) {
		int N = g.length;
		int[] disc = new int[N];
		int[] low = new int[N];
		Arrays.fill(disc, -1);
		Arrays.fill(low, -1);
		boolean stackMember[] = new boolean[N];
		LinkedList<Integer> st = new LinkedList<>();
		LinkedList<List<Integer>> ans = new LinkedList<>();
		ans.add(new LinkedList<>());
		for (int i = 0; i<N; i++)
			if (disc[i] == -1)
				SCCUtil(i, low, disc, stackMember, st, 0, g, ans);
		ans.pollLast();
		return ans;
	}private static int SCCUtil(int s, int[] low, int[] disc, boolean[] stackMember, LinkedList<Integer> st, int time, List<Integer>[] g, List<List<Integer>> ans) {
		disc[s] = time;
		low[s] = time;
		time++;
		stackMember[s] = true;
		st.push(s);
		for(int i: g[s]){
			if (disc[i] == -1) {
				time = SCCUtil(i, low, disc, stackMember, st, time, g, ans);
				low[s] = min(low[s], low[i]);
			} else if(stackMember[i] == true)
				low[s] = min(low[s], disc[i]);
		}
		int w = -1;
		if (low[s] == disc[s]) {
			while (w != s) {
				w = st.pop();
				ans.get(ans.size()-1).add(w);
				stackMember[w] = false;
			}
			ans.add(new LinkedList<>());
		}
		return time;
	}
	// depth of tree in arr[0], par of nodes in arr[1]
	private static int[][] depthPar(int s, List<Integer>[] g) {
		int[][] ans = new int[2][g.length];
		depthParDFS(g, s, -1, ans);
		return ans;
	}private static void depthParDFS(List<Integer>[] g, int s, int p, int[][] d) {
		d[1][s] = p;
		for(int i: g[s]) if(i != p) {
			d[0][i] = d[0][s]+1;
			depthParDFS(g, i, s, d);
		}
	}
	// compresses nodes with 1 child
	// new tree in arr[0], list of previous nodes that compress to new nodes in arr[1]
	private static List<Integer>[][] treeComp(List<Integer>[] g){
		int N = g.length;
		if(N == 1) {
			List<Integer>[][] ans = new List[2][1];
			ans[0][0] = new LinkedList<>();
			ans[1][0] = new LinkedList<>();
			ans[1][0].add(0);
			return ans;
		}
		int[] map = new int[N];
		int K = treeCompGetCount(g, 0, -1, map, 0);
		List<Integer>[][] ans = new List[2][K];
		for(int i = 0; i<K; i++) {
			ans[0][i] = new LinkedList<>();
			ans[1][i] = new LinkedList<>();
		}
		treeCompDFS(g, map, ans, 0);
		return ans;
	}private static int treeCompGetCount(List<Integer>[] g, int s, int p, int[] map, int time) {
		g[s].remove((Integer)p);
		if(p == -1 || g[p].size() != 1) map[s] = time++; else map[s] = -1;
		for(int i: g[s]) if(i != p) time = treeCompGetCount(g, i, s, map, time);
		return time;
	}private static void treeCompDFS(List<Integer>[] g, int[] map, List<Integer>[][] ret, int s) {
		int curr = s;
		while(g[curr].size() == 1) {
			ret[1][map[s]].add(curr);
			curr = g[curr].get(0);
		}
		ret[1][map[s]].add(curr);
		for(int i: g[curr]) {
			ret[0][map[s]].add(map[i]);
			treeCompDFS(g, map, ret, i);
		}
	}
	// detects cycle
	private static boolean hasCycle(List<Integer>[] g) {
		byte[] vis = new byte[g.length];
		for(int i = 0; i<g.length; i++) if(vis[i] == 0 && hasCycleHelper(g, i, vis)) return true;
		return false;
	}private static boolean hasCycleHelper(List<Integer>[] g, int s, byte[] vis) {
		vis[s] = 1;
		for(int i: g[s]) if(vis[i] == 1) return true;
		else if(vis[i] == 0 && hasCycleHelper(g, i, vis)) return true;
		vis[s] = 2;
		return false;
	}
	// counts amount of numbers using treemap
	private static class Cnt<T> {
		
		public TreeMap<T, Long> map;
		boolean first = true;
		public Cnt() {}
		
		public long get(T num) {
			if(first) {
				if(num instanceof Long) map = new TreeMap<>((a, b) -> Long.compare((long)a, (long)b));
				else map = new TreeMap<>();
				first = false;
			}
			Long get = map.get(num);
			if (get == null)
				return 0;
			return get;
		}
		
		public void add(T num) {
			add(num, 1);
		}
		
		public void rem(T num) {
			add(num, -1);
		}
		
		public void rem(T num, long cnt) {
			add(num, -cnt);
		}
		
		public void add(T num, long cnt) {
			if(first) {
				if(num instanceof Long) map = new TreeMap<>((a, b) -> Long.compare((long)a, (long)b));
				else map = new TreeMap<>();
				first = false;
			}
			Long get = map.get(num);
			if (get == null)
				get = 0L;
			get += cnt;
			if (get == 0)
				map.remove(num);
			else
				map.put(num, get);
		}
		public boolean isEmpty() {
			if(map == null) return true;
			return map.isEmpty();
		}
		public T min() {
			if(map == null) return null;
			return map.isEmpty() ? null:map.firstKey();
		}
		public T max() {
			if(map == null) return null;
			return map.isEmpty() ? null:map.lastKey();
		}
		@Override
		public String toString() {
			return map.toString();
		}
	}
	// 1 line convenience functions
	private static void print(int... a) {
		System.out.println(a.length == 0 ? "":Arrays.toString(a).replaceAll("2147483647", "inf"));
	}
	private static void print(long... a) {
		System.out.println(a.length == 0 ? "":Arrays.toString(a).replaceAll("2147483647", "inf"));
	}
	private static void out(int[] a) {
		for(int i: a) out.print(i+" ");
		out.println();
	}
	private static void out(long[] a) {
		for(long l: a) out.print(l+" ");
		out.println();
	}
	private static void outLn(int[] a) {
		for(int i: a) out.println(i);
	}
	private static void outLn(long[] a) {
		for(long l: a) out.println(l);
	}
	// basic math
	private static int gcd(int a, int b) {
		while(b > 0) {
			int t = a%b;
			a = b;
			b = t;
		}
		return a;
	}
	private static int max(int... x) {
		for (int i = 1; i < x.length; i++)
			x[0] = Math.max(x[0], x[i]);
		return x[0];
	}
	private static int min(int... x) {
		for (int i = 1; i < x.length; i++)
			x[0] = Math.min(x[0], x[i]);
		return x[0];
	}
	private static long max(long... x) {
		for (int i = 1; i < x.length; i++)
			x[0] = Math.max(x[0], x[i]);
		return x[0];
	}
	private static long min(long... x) {
		for (int i = 1; i < x.length; i++)
			x[0] = Math.min(x[0], x[i]);
		return x[0];
	}
	// modular arithmatic
	private static class Mod {
		private Mod() {
			
		}
		public static void fact(int max) {
			fact = new long[max+1];
			fact[0] = 1;
			for(int i = 1; i<=max; i++) fact[i] = (fact[i-1]*i)%mod;
		}
		public static long nCk(int n, int k) {
			return (fact[n]*((inv(fact[k])*inv(fact[n-k])%mod)))%mod;
		}
		public static long mul(long a, long b, long mod) {
			long ret = 0;
			while(b > 0) {
				if((b&1) == 1)
					ret = (ret+a)%mod;
				a = (a<<1)%mod;
				b>>=1;
			}
			return ret;
		}
		public static long inv(long x) {
			return pow(x, mod - 2, mod);
		}
		public static long inv(long x, long mod) {
			return pow(x, mod - 2, mod);
		}
		public static long pow(long x, long n) {
			return pow(x, n, mod);
		}
		public static long pow(long x, long n, long mod) {
			x %= mod;
			long res = 1;
			while (n > 0) {
				if ((n & 1) == 1)
					res = res * x % mod;
				x = x * x % mod;
				n >>= 1;
			}
			return res;
		}
	}
	// binary search (last true, first true)
	private static class BS {
		public interface Oper {
			boolean test(long num);
		}
		
		private BS() {
			
		}
		
		public static long last(long lo, long hi, Oper oper) {
			lo--;
			while (lo < hi) {
				long mid = lo + (hi - lo + 1) / 2;
				if (oper.test(mid)) {
					lo = mid;
				} else {
					hi = mid - 1;
				}
			}
			return lo;
		}
		
		public static long first(long lo, long hi, Oper oper) {
			hi++;
			while (lo < hi) {
				long mid = lo + (hi - lo) / 2;
				if (oper.test(mid)) {
					hi = mid;
				} else {
					lo = mid + 1;
				}
			}
			return lo;
		}
	}
	// linked lists that can merge in O(1)
	private static class Merge<T> implements Iterable<T> {
		private class Node {
			public T num;
			public Node next = null;
			
			public Node(T num) {
				this.num = num;
			}
		}
		
		private class mergeIterator implements Iterator<T> {
			private Node s;
			
			public mergeIterator(Node s) {
				this.s = s;
			}
			
			@Override
			public boolean hasNext() {
				return s != null;
			}
			
			@Override
			public T next() {
				T ret = s.num;
				s = s.next;
				return ret;
			}
		}
		
		private Node s, e;
		private int size;
		
		public Merge() {
			s = e = null;
			size = 0;
		}
		
		public void addF(T n) {
			if (s == null)
				s = e = new Node(n);
			else {
				Node p = new Node(n);
				p.next = s;
				s = p;
			}
			size++;
		}
		
		public void add(T n) {
			if (s == null)
				s = e = new Node(n);
			else {
				e.next = new Node(n);
				e = e.next;
			}
			size++;
		}
		
		public void addAll(Merge<T> m) {
			if (m == this)
				return;
			if (e == null)
				s = e = m.s;
			else
				e.next = m.s;
			e = m.e;
			size += m.size;
		}
		
		public int size() {
			return size;
		}
		
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append("[");
			for (T i : this)
				sb.append(i + ", ");
			if (sb.length() > 1)
				sb.delete(sb.length() - 2, sb.length());
			sb.append("]");
			return sb.toString();
		}
		
		@Override
		public Iterator<T> iterator() {
			return new mergeIterator(s);
		}
		
		public void clear() {
			s = e = null;
			size = 0;
		}
	}
	//DSU but can store memory in each component
	private static class DSU<Val> {
		private Val[] vals;
		private int[] par, size;
		private Merge<Integer>[] all;
		private int cc;
		private Comb<Val> o;
		public DSU(int N, boolean storeAll) {this(N, null, storeAll);}
		public DSU(int N, Comb<Val> o, Def<Val[]> def) {this(N, o, false);}
		public DSU(int N) {this(N, null, false);}
		public DSU(int N, Comb<Val> o, boolean storeAll) {
			par = new int[N];
			size = new int[N];
			cc = N;
			Arrays.fill(par, -1);
			Arrays.fill(size, 1);
			this.o = o;
			if(o != null) vals = (Val[]) new Object[N];
			if(storeAll) {
				all = new Merge[N];
				for(int i = 0; i<N; i++) {
					all[i] = new Merge();
					all[i].add(i);
				}
			}
		}
		
		public Val getVal(int num) {
			return vals[get(num)];
		}
		
		public int size(int num) {
			return size[get(num)];
		}
		
		public int get(int num) {
			return par[num] == -1 ? num : (par[num] = get(par[num]));
		}
		
		public boolean isSame(int x, int y) {
			return get(x) == get(y);
		}
		
		public boolean unite(int x, int y) {
			int p1 = get(x), p2 = get(y);
			if (p1 == p2)
				return false;
			Val next = o == null ? null:o.oper(vals[p1], vals[p2]);
			Merge<Integer> a = all == null ? null:all[p1], b = all == null ? null:all[p2];
			if (size[p1] < size[p2]) {
				int s = p2;
				p2 = p1;
				p1 = s;
				Merge<Integer> v = a;
				a = b;
				b = v;
			}
			size[p1] += size[p2];
			par[p2] = p1;
			cc--;
			if(vals != null) vals[p1] = next;
			if(a != null)
				a.addAll(b);
			return true;
		}
		
		public int getCC() {
			return cc;
		}
		
		public void set(int num, Val curr) {
			vals[get(num)] = curr;
		}
		
		public Merge<Integer> getAll(int num) {
			return all[get(num)];
		}
	}
	// pairs 2 objects into 1 (can be used in hashmap)
	private static class Two<A, B> {
		public A a;
		public B b;
		
		public Two(A a, B b) {
			this.a = a;
			this.b = b;
		}
		
		@Override
		public boolean equals(Object obj) {
			if (!(obj instanceof Two))
				return false;
			Two curr = (Two) obj;
			return curr.a.equals(a) && curr.b.equals(b);
		}
		
		@Override
		public int hashCode() {
			long seed = a.hashCode();
			seed = seed << 32;
			seed |= b.hashCode();
			Random r = new Random();
			r.setSeed(seed);
			return r.nextInt();
		}
		
		@Override
		public String toString() {
			return "(" + a.toString() + ", " + b.toString() + ")";
		}
	}
	// Lazy segment tree for all operations (sparse)
    private static class ALST<Val, Lz> {
		private final long l, r;
		private ALST<Val, Lz> left, right;
		private Val val;
		private Lz lz;
		private final Def<Val> def;
		private final DefLz<Lz> defLz;
		private Comb<Val> comb;
		private Prop<Val, Lz> prop;
		private LZ<Lz> lzOper;
		public ALST(long N, Comb<Val> comb, Prop<Val, Lz> prop, LZ<Lz> lzOper, Def<Val> def, DefLz<Lz> defLz)
			{this(0, N-1, comb, prop, lzOper, def, defLz);}
		private ALST(long l, long r, Comb<Val> comb, Prop<Val, Lz> prop, LZ<Lz> lzOper, Def<Val> def, DefLz<Lz> defLz) {
			this.l = l;
			this.r = r;
			this.comb = comb;
			this.prop = prop;
			this.lzOper = lzOper;
			val = def.get(r-l+1);
			lz = defLz.get();
			this.def = def;
			this.defLz = defLz;
		}
		public Val all() {
			return val;
		}
		public void push(long s, Lz num) {push(s, s, num);}
		public void push(long a, long b, Lz num) {
			if(a == l && b == r) {push(num); return;}
			long mid = (l+r)>>1;
			if(left == null) left = new ALST<Val, Lz>(l, mid, comb, prop, lzOper, def, defLz);
			if(right == null) right = new ALST<Val, Lz>(mid+1, r, comb, prop, lzOper, def, defLz);
			prop();
			if(b <= mid) left.push(a, b, num);
			else if(a > mid) right.push(a, b, num);
			else {
				left.push(a, mid, num);
				right.push(mid+1, b, num);
			}
			val = comb.oper(left.val, right.val);
		}
		public void set(long s, Val num) {
			if(l == r) {
				val = num;
				return;
			}
			long mid = (l+r)>>1;
			if(left == null) left = new ALST<Val, Lz>(l, mid, comb, prop, lzOper, def, defLz);
			if(right == null) right = new ALST<Val, Lz>(mid+1, r, comb, prop, lzOper, def, defLz);
			prop();
			if(s > mid) right.set(s, num);
			else left.set(s, num);
			val = comb.oper(left.val, right.val);
		}
		public Val get(long a, long b) {
			if(a == l && b == r) return all();
			long mid = (l+r)>>1;
			if(left == null) left = new ALST<Val, Lz>(l, mid, comb, prop, lzOper, def, defLz);
			if(right == null) right = new ALST<Val, Lz>(mid+1, r, comb, prop, lzOper, def, defLz);
			prop();
			if(b <= mid) return left.get(a, b);
			if(a > mid) return right.get(a, b);
			return comb.oper(left.get(a, mid), right.get(mid+1, b));
		}
		private void prop() {
			left.push(lz);
			right.push(lz);
			lz = defLz.get();
		}
		private void push(Lz num) {
			lz = lzOper.oper(num, lz);
			val = prop.oper(num, val, r-l+1);
		}
	}
    // Lazy segment tree for add, set, max, min, sum (sparse)
	private static class LZST {
		private class Node {
			public long l, r;
			public Node left, right;
			public long val = 0, max = 0, min = 0, add = 0;
			public boolean isSet = false;
			public Node(long a, long b) {
				l = a;
				r = b;
			}
			public void set(long num) {
				isSet = true;
				add = max = min = num;
				val = num*(r-l+1);
			}
			public void add(long num) {
				add+=num;
				val+=num*(r-l+1);
				max+=num;
				min+=num;
			}
			public void prop() {
				long mid = (l+r)>>1;
				if(left == null) left = new Node(l, mid);
				if(right == null) right = new Node(mid+1, r);
				if(isSet) {
					isSet = false;
					if(l != r) {
						left.set(add);
						right.set(add);
					}
				}else if(add != 0) {
					if(l != r) {
						left.add(add);
						right.add(add);
					}
				}
				add = 0;
			}
			public void upd() {
				val = left.val+right.val;
				min = Math.min(left.min, right.min);
				max = Math.max(left.max, right.max);
			}
		}
		Node top;
		public LZST(long N) {
			assert(N > 0);
			top = new Node(0, N-1);
		}
		private void set(long s, long e, long num, Node curr) {
			if(curr.l == s && curr.r == e) {
				curr.set(num);
				return;
			}
			curr.prop();
			if(e <= curr.left.r) set(s, e, num, curr.left);
			else if(s >= curr.right.l) set(s, e, num, curr.right);
			else{
				set(s, curr.left.r, num, curr.left);
				set(curr.right.l, e, num, curr.right);
			}
			curr.upd();
		}
		private void add(long s, long e, long num, Node curr) {
			if(curr.l == s && curr.r == e) {
				curr.add(num);
				return;
			}
			curr.prop();
			if(e <= curr.left.r) add(s, e, num, curr.left);
			else if(s >= curr.right.l) add(s, e, num, curr.right);
			else{
				add(s, curr.left.r, num, curr.left);
				add(curr.right.l, e, num, curr.right);
			}
			curr.upd();
		}
		private long sum(long s, long e, Node curr) {
			if(curr.l == s && curr.r == e) return curr.val;
			curr.prop();
			if(e <= curr.left.r) return sum(s, e, curr.left);
			if(s >= curr.right.l) return sum(s, e, curr.right);
			return sum(s, curr.left.r, curr.left)+sum(curr.right.l, e, curr.right);
		}
		private long max(long s, long e, Node curr) {
			if(curr.l == s && curr.r == e) return curr.max;
			curr.prop();
			if(e <= curr.left.r) return max(s, e, curr.left);
			if(s >= curr.right.l) return max(s, e, curr.right);
			return Math.max(max(s, curr.left.r, curr.left), max(curr.right.l, e, curr.right));
		}
		private long min(long s, long e, Node curr) {
			if(curr.l == s && curr.r == e) return curr.min;
			curr.prop();
			if(e <= curr.left.r) return min(s, e, curr.left);
			if(s >= curr.right.l) return min(s, e, curr.right);
			return Math.min(min(s, curr.left.r, curr.left), min(curr.right.l, e, curr.right));
		}
		public long get(long s) {
			assert(s >= top.l && s <= top.r);
			Node curr = top;
			LinkedList<Node> stk = new LinkedList<>();
			while(curr.l != curr.r) {
				stk.push(curr);
				curr.prop();
				if(s <= curr.left.r) curr = curr.left;
				else curr = curr.right;
			}
			while(!stk.isEmpty()) stk.pop().upd();
			return curr.val;
		}
		public long sum(long s, long e) {
			assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
			return sum(s, e, top);
		}
		public long max(long s, long e) {
			assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
			return max(s, e, top);
		}
		public long min(long s, long e) {
			assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
			return min(s, e, top);
		}
		public void add(long s, long e, long num) {
			assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
			add(s, e, num, top);
		}
		public void add(long s, long num) {
			assert(s >= top.l && s <= top.r);
			add(s, s, num);
		}
		public void set(long s, long e, long num) {
			assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
			set(s, e, num, top);
		}
		public void set(long s, long num) {
			assert(s >= top.l && s <= top.r);
			set(s, s, num);
		}
		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder("[");
			for(int i = 0; i<=top.r; i++) sb.append(get(i)+(i == top.r ? "]":", "));
			return sb.toString();
		}
	}
	// normal segment tree with all associative operations
	private static class AST<Val> {
		private class Node<Val> {
			public Val val;
			public Node<Val> p, le, ri;
			public int l, r;
			
			public Node(int l, int r) {
				this.l = l;
				this.r = r;
			}
		}
		
		private final Comb<Val> oper;
		private final Node<Val> top;
		private final Node<Val>[] last;
		public AST(int n, Comb<Val> oper) {
			this.oper = oper;
			top = new Node<>(0, n - 1);
			last = new Node[n];
			getNode(top);
		}
		
		private void getNode(Node<Val> t) {
			if (t.l == t.r) {
				last[t.l] = t;
				return;
			}
			int mid = (t.l + t.r) >> 1;
			t.le = new Node<>(t.l, mid);
			t.ri = new Node<>(mid + 1, t.r);
			getNode(t.le);
			getNode(t.ri);
			t.le.p = t.ri.p = t;
		}
		
		public void set(int k, Val num) {
			Node<Val> t = last[k];
			t.val = num;
			t = t.p;
			while (t != null) {
				if (t.le.val != null && t.ri.val != null)
					t.val = oper.oper(t.le.val, t.ri.val);
				else return;
				t = t.p;
			}
		}
		
		public Val all() {
			return top.val;
		}
		
		public Val get(int a) {
			return last[a].val;
		}
		
		public Val get(int a, int b) {
			if (a == b)
				return get(a);
			return get(a, b, top);
		}
		
		private Val get(int a, int b, Node<Val> n) {
			if (a == n.l && b == n.r)
				return n.val;
			Node<Val> l = n.le, r = n.ri;
			if (l.l <= a && l.r >= b)
				return get(a, b, l);
			if (r.l <= a && r.r >= b)
				return get(a, b, r);
			Val left = get(a, l.r, l), right = get(r.l, b, r);
			return oper.oper(left, right);
		}
	}
	// binary indexed tree (just sum)
	private static class BIT {
		private final long[] bit;
		private final long[] arr;
		private final int len;
		private long all;
		
		public BIT(int len) {
			bit = new long[len + 1];
			arr = new long[len];
			this.len = len;
			all = 0;
		}
		
		public long get(int ind) {
			return arr[ind];
		}
		
		public void set(int ind, long val) {
			add(ind, val - arr[ind]);
		}
		
		public void add(int ind, long val) {
			all+=val;
			arr[ind] += val;
			ind++;
			for (; ind <= len; ind += ind & -ind)
				bit[ind] += val;
		}
		
		public long suf(int ind) {
			return all-(ind == 0 ? 0:prev(ind-1));
		}
		
		public long prev(int ind) {
			if(ind == len-1) return all;
			ind++;
			long sum = 0;
			for (; ind > 0; ind -= ind & -ind)
				sum += bit[ind];
			return sum;
		}
		
		public long sum(int a, int b) {
			return prev(b) - (a == 0 ? 0 : prev(a - 1));
		}
		@Override
		public String toString() {
			StringBuilder ret = new StringBuilder();
			ret.append("[");
			for(int i = 0; i<len; i++) ret.append(get(i)+(i == len-1 ? "]":", "));
			return ret.toString();
		}
	}
	// static range queries (logn preprocessing, constant query)
    private static class SRQ<T> {
    	private static int lg(int n) { return 31 - Integer.numberOfLeadingZeros(n); }
    	private T[][] data;
    	private T[] nums;
    	private Comb<T> oper;
    	public SRQ(T[] nums, Comb<T> oper) {
    		this.nums = nums;
    		this.oper = oper;
            int n = nums.length;
            int logn = lg(n) + 1;
            data = (T[][]) new Object[logn][n];
            for(int k = 1; k <= n; k++) {
                int rad = 1, i = 0;
                while(k % (2 * rad) == 0) {
                    rad *= 2;
                    i++;
                }
                data[i][k - 1] = nums[k - 1];
                for(int j = k - 2; j >= k - rad; j--)
                    data[i][j] = oper.oper(nums[j], data[i][j + 1]);
                if(k < n) data[i][k] = nums[k];
                for(int j = k + 1; j < n && j < k + rad; j++)
                    data[i][j] = oper.oper(data[i][j - 1], nums[j]);
            }        
        }
    	public T get(int l, int r) {
    		if(l == r) return nums[l];
    		int ind = lg(l^r);
    		return oper.oper(data[ind][l], data[ind][r]);
    	}
    }
    // normal segment tree (order dosen't matter)
	private static class ST {
		public interface Oper {
			long solve(long a, long b);
		}
		
		private long[] tree;
		public final int n;
		private final Oper oper;
		private final int def;
		
		public ST(int n, Oper oper, int def) {
			this.n = n;
			tree = new long[n << 1];
			this.oper = oper;
			this.def = def;
			for (int i = 0; i < n; i++)
				set(i, def);
		}
		
		public ST(int n, Oper oper) {
			this(n, oper, 0);
		}
		
		public ST(int n) {
			this(n, (a, b) -> Math.min(a, b), 0);
		}
		
		public long get(int a, int b) {
			if (a == b)
				return tree[a + n];
			if (b < a)
				return def;
			a += n;
			b += n;
			long curr = 0;
			boolean checked = false;
			while (a <= b) {
				if ((a & 1) == 1) {
					if (checked)
						curr = oper.solve(curr, tree[a++]);
					else
						curr = tree[a++];
					checked = true;
				}
				if ((b & 1) == 0) {
					if (checked)
						curr = oper.solve(curr, tree[b--]);
					else
						curr = tree[b--];
					checked = true;
				}
				a = a >> 1;
			b = b >> 1;
			}
			return curr;
		}
		
		public long all() {
			return get(0, n-1);
		}
		
		public void set(int index, long val) {
			index += n;
			tree[index] = val;
			for (index = index >> 1; index >= 1; index = index >> 1)
				tree[index] = oper.solve(tree[index << 1], tree[(index << 1) + 1]);
		}
		
		public long get(int index) {
			return tree[index + n];
		}
		
		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append("[");
			for (int i = 0; i < n; i++) {
				sb.append(get(i));
				if (i != n - 1)
					sb.append(", ");
			}
			sb.append("]");
			return sb.toString();
		}
	}
	// FastIO reader
	private static class FastIO {
		InputStream dis;
		byte[] buffer = new byte[500007];
		int pointer = 0, end = 0;

		public FastIO(String fileName) throws Exception {
			dis = new FileInputStream(fileName);
		}

		public char nextChar() throws Exception {
			return next().charAt(0);
		}

		public FastIO(InputStream is) throws Exception {
			dis = is;
		}

		public int nextInt() throws Exception {
			int ret = 0;
			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}
			return (negative) ? -ret : ret;
		}

		public long nextLong() throws Exception {
			long ret = 0;
			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			boolean negative = false;
			if (b == '-') {
				negative = true;
				b = nextByte();
			}
			while (b >= '0' && b <= '9') {
				ret = 10 * ret + b - '0';
				b = nextByte();
			}
			return (negative) ? -ret : ret;
		}

		private byte nextByte() throws Exception {
			while (pointer >= end) {
				end = dis.read(buffer, 0, buffer.length);
				pointer = 0;
			}
			return buffer[pointer++];
		}

		public double nextDouble() throws Exception {
			return Double.parseDouble(next());
		}

		public String next() throws Exception {
			StringBuffer ret = new StringBuffer();
			byte b;
			do {
				b = nextByte();
			} while (b <= ' ');
			while (b > ' ') {
				ret.appendCodePoint(b);
				b = nextByte();
			}
			return ret.toString();
		}
		
		public long[] longArr(int len) throws Exception{
			long[] ans = new long[len];
			for (int i = 0; i < len; i++)
				ans[i] = nextLong();
			return ans;
		}
		
		public int[] nextArr() throws Exception {
			return nextArr(nextInt());
		}

		public int[] nextArr(int len) throws Exception {
			int[] ans = new int[len];
			for (int i = 0; i < len; i++)
				ans[i] = nextInt();
			return ans;
		}

		public List<Integer>[] nextTree() throws Exception {
			return nextTree(nextInt());
		}

		public LinkedList<Integer>[] nextTree(int n) throws Exception {
			return nextGraph(n, n - 1);
		}
		
		public LinkedList<int[]>[] weightGraph(int n, int m) throws Exception{
			return weightGraph(n, m, false);
		}
		
		public LinkedList<int[]>[] weightGraph(int n, int m, boolean directed) throws Exception {
			LinkedList<int[]>[] ans = new LinkedList[n];
			for(int i = 0; i<n; i++) ans[i] = new LinkedList<>();
			for(int i = 0; i<m; i++) {
				int a = nextInt()-1, b = nextInt()-1, w = nextInt();
				ans[a].add(new int[] {b, w});
				if(!directed) ans[b].add(new int[] {a, w});
			}
			return ans;
		}
		
		public LinkedList<Integer>[] nextGraph(int n, int m) throws Exception {
			return nextGraph(n, m, false);
		}
		
		public LinkedList<Integer>[] nextGraph(int n, int m, boolean directed) throws Exception {
			LinkedList<Integer>[] ans = new LinkedList[n];
			for (int i = 0; i < n; i++)
				ans[i] = new LinkedList<>();
			for (int i = 0; i < m; i++) {
				int a = nextInt() - 1, b = nextInt() - 1;
				ans[a].add(b);
				if(!directed) ans[b].add(a);
			}
			return ans;
		}
		
		public char[] chars() throws Exception {
			return next().toCharArray();
		}
	}
}

Compilation message (stderr)

Note: mecho.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 21 / 100