In this HackerEarth ( Problem E ) Pikachu and Champions League problem solution Pikachu has already defeated so many legendary Pokemon, and is now organizing the Champions League where champions of all Conferences are going to battle for glory.
There are N Conferences around the world, connected by exactly N - 1 bidirectional roads. It is always possible to reach one Conference from another.
To choose the Champion of Champions, Pikachu chooses a set S of Conferences. Now, each Conference champion in S battles with every other Conference champion in S and for each battle, one of the champion has to travel. Pikachu wants to know the maximum distance any champion would travel to battle.
Pikachu has thought of Q such sets. He wants to know the maximum distance for each set so that he can choose the least tiresome set.
HackerEarth ( Problem E ) Pikachu and Champions League problem solution.
#include<bits/stdc++.h>
using namespace std;
typedef long long lld;
#define N 500005
#define LOGN 20
lld level[N];
vector<lld> adj[N];
struct LCA{
lld p[N][LOGN];
void dfs(lld x){
for(lld i=1;i<LOGN;i++) p[x][i]=p[p[x][i-1]][i-1];
for(auto i:adj[x]) if(!level[i]) p[i][0]=x,level[i]=level[x]+1,dfs(i);
}
lld lca(lld u,lld v) {
if(level[u]<level[v]) swap(u,v);
for(lld i=LOGN-1;i>=0;i--) if(level[p[u][i]]>=level[v]) u=p[u][i];
if(u==v) return u;
for(lld i=LOGN-1;i>=0;i--) if(p[u][i]!=p[v][i]) u=p[u][i],v=p[v][i];
return p[u][0];
}
lld dist(lld u,lld v) {
lld temp=lca(u,v);
return level[u]-level[temp]+level[v]-level[temp];
}
} lc;
lld dfs_order[N],timer;
void calc(lld x,lld par) {
dfs_order[x] = (++timer);
for(auto i:adj[x]) if(i!=par) calc(i,x);
}
bool comp(lld x,lld y) {
return (dfs_order[x] < dfs_order[y]);
}
lld query[N],par[N],dp1[N],dp2[N];
vector<lld> query_tree[N];
int main() {
lld n,k,q,tot=0,x,y;
cin>>n>>q;
assert(n>=1 and n<=500000);
assert(q>=1 and q<=500000);
for(lld i=1;i<n;i++) {
cin>>x>>y;
assert(x>=1 and x<=n);
assert(y>=1 and y<=n);
adj[x].push_back(y);
adj[y].push_back(x);
}
adj[0].push_back(1), adj[1].push_back(0);
level[0] = 1;
lc.dfs(0);
calc(0,-1);
while(q--) {
cin>>k;
tot += k;
assert(k>=2 and k<=500000);
assert(tot<=500000);
for(lld i=1;i<=k;i++) cin>>query[i];
sort(query+1,query+k+1,comp);
set<lld> tmp;
for(lld i=1;i<=k;i++) tmp.insert(query[i]);
for(lld i=2;i<=k;i++) tmp.insert(lc.lca(query[i-1],query[i]));
vector<lld> final;
for(auto i:tmp) final.push_back(i);
sort(final.begin(), final.end(), comp);
stack<lld> stk;
stk.push(0);
for(auto i:final) {
while(!stk.empty() and lc.lca(stk.top(), i) != stk.top()) stk.pop();
par[i] = stk.top();
query_tree[stk.top()].push_back(i); //Now the tree only contains the children
stk.push(i);
}
//Note: Here taking vertices in reverse order is basically simulating the dfs
lld tot_size = (lld)(final.size()), ans = 0;
for(lld i=tot_size-1;i>=0;i--) {
lld curr = final[i], max1 = -1, max2 = -1;
for(auto child:query_tree[curr]) {
lld curr_max = lc.dist(child,curr) + dp1[child];
dp1[curr] = max(dp1[curr], curr_max);
if(curr_max >= max1) {
max2 = max1, max1 = curr_max;
}
else if(curr_max >= max2) {
max2 = curr_max;
}
}
if(max1 != -1 and max2 != -1) dp2[curr] = max1 + max2;
else dp2[curr] = -1;
if(curr) ans = max(ans, max(dp1[curr], dp2[curr]));
}
cout<<ans<<endl;
for(lld i=tot_size-1;i>=0;i--) {
lld curr = final[i];
query_tree[curr].clear();
dp1[curr] = dp2[curr] = 0;
}
}
}Second solution
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.HashMap;
import java.io.IOException;
import java.util.Stack;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*
* @author lewin
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
TaskA solver = new TaskA();
solver.solve(1, in, out);
out.close();
}
static class TaskA {
int[] diam(int node, int par, List<CompressedTree.Edge>[] g) {
int deep1 = 0, deep2 = 0;
int diam = 0;
for (CompressedTree.Edge next : g[node]) {
if (next.to == par) continue;
int[] r = diam(next.to, node, g);
int len = next.weight;
r[1] += len;
diam = Math.max(diam, r[0]);
if (r[1] > deep1) {
deep2 = deep1;
deep1 = r[1];
} else if (r[1] > deep2) {
deep2 = r[1];
}
}
diam = Math.max(diam, deep1 + deep2);
return new int[]{diam, deep1};
}
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.nextInt(), q = in.nextInt();
List<Integer>[] graph = LUtils.genArrayList(n);
for (int i = 0; i < n - 1; i++) {
int a = in.nextInt() - 1, b = in.nextInt() - 1;
graph[a].add(b);
graph[b].add(a);
}
CompressedTree ct = new CompressedTree(graph);
while (q-- > 0) {
int s = in.nextInt();
int[] nodes = in.readIntArrayAndDecrementOne(s);
out.println(diam(0, -1, ct.compressedTree(nodes))[0]);
}
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1 << 16];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int[] readIntArrayAndDecrementOne(int tokens) {
int[] ret = new int[tokens];
for (int i = 0; i < tokens; i++) {
ret[i] = nextInt() - 1;
}
return ret;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
static class LUtils {
public static <E> List<E>[] genArrayList(int size) {
return Stream.generate(ArrayList::new).limit(size).toArray(List[]::new);
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void println(int i) {
writer.println(i);
}
}
static class LcaSchieberVishkin {
int[] parent;
public int[] preOrder;
int[] I;
int[] head;
int[] A;
int time;
public LcaSchieberVishkin(List<Integer>[] tree, int root) {
int n = tree.length;
preOrder = new int[n];
I = new int[n];
head = new int[n];
A = new int[n];
parent = new int[n];
dfs1(tree, root, -1);
dfs2(tree, root, -1, 0);
}
void dfs1(List<Integer>[] tree, int u, int p) {
parent[u] = p;
I[u] = preOrder[u] = time++;
for (int v : tree[u]) {
if (v == p) continue;
dfs1(tree, v, u);
if (Integer.lowestOneBit(I[v]) > Integer.lowestOneBit(I[u])) {
I[u] = I[v];
}
}
head[I[u]] = u;
}
void dfs2(List<Integer>[] tree, int u, int p, int up) {
A[u] = up | Integer.lowestOneBit(I[u]);
for (int v : tree[u]) {
if (v == p) continue;
dfs2(tree, v, u, A[u]);
}
}
int enterIntoStrip(int x, int hz) {
if (Integer.lowestOneBit(I[x]) == hz)
return x;
int hw = Integer.highestOneBit(A[x] & (hz - 1));
return parent[head[I[x] & (~hw + 1) | hw]];
}
public int lca(int x, int y) {
int hb = I[x] == I[y] ? Integer.lowestOneBit(I[x]) : Integer.highestOneBit(I[x] ^ I[y]);
int hz = Integer.lowestOneBit(A[x] & A[y] & (~hb + 1));
int ex = enterIntoStrip(x, hz);
int ey = enterIntoStrip(y, hz);
return preOrder[ex] < preOrder[ey] ? ex : ey;
}
}
static class CompressedTree {
public int[] depth;
int[] tin;
LcaSchieberVishkin lc;
int midx;
HashMap<Integer, Integer> xx;
void dfs(int node, int par, List<Integer>[] graph) {
depth[node] = par == -1 ? 0 : (depth[par] + 1);
for (int next : graph[node]) {
if (next == par) continue;
dfs(next, node, graph);
}
}
public CompressedTree(List<Integer>[] graph) {
depth = new int[graph.length];
dfs(0, -1, graph);
lc = new LcaSchieberVishkin(graph, 0);
tin = lc.preOrder;
}
void addToMap(int item) {
if (xx.containsKey(item)) return;
xx.put(item, midx++);
}
void addEdge(List<CompressedTree.Edge>[] ret, int a, int b) {
if (a == b) return;
int weight = Math.abs(depth[a] - depth[b]);
int ta = xx.get(a), tb = xx.get(b);
ret[ta].add(new CompressedTree.Edge(tb, weight));
ret[tb].add(new CompressedTree.Edge(ta, weight));
}
public List<CompressedTree.Edge>[] compressedTree(int[] nodes) {
int n = nodes.length;
Integer[] ss = new Integer[n];
for (int i = 0; i < n; i++) ss[i] = nodes[i];
Arrays.sort(ss, Comparator.comparingInt(x -> tin[x]));
midx = 0;
xx = new HashMap<>();
for (int i = 0; i < n; i++) {
addToMap(ss[i]);
}
int[] lcas = new int[n - 1];
for (int i = 0; i + 1 < n; i++) {
lcas[i] = lc.lca(ss[i], ss[i + 1]);
addToMap(lcas[i]);
}
List<CompressedTree.Edge>[] ret = LUtils.genArrayList(midx);
ArrayList<Integer> r = new ArrayList<>(xx.keySet());
r.sort(Comparator.comparingInt(x -> tin[x]));
Stack<Integer> pstack = new Stack<>();
for (int x : r) {
while (!pstack.empty() && lc.lca(pstack.peek(), x) != pstack.peek()) {
pstack.pop();
}
if (!pstack.empty()) addEdge(ret, pstack.peek(), x);
pstack.push(x);
}
return ret;
}
public static class Edge {
public int to;
public int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
}
}
0 Comments