| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 117094 | Bruteforceman | Min-max tree (BOI18_minmaxtree) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.util.*;
import java.io.*;
class MinMaxTree {
public static void main(String [] args) {
Solver s = new Solver();
s.solve();
}
}
class Solver {
Reader in = new Reader ();
Writer out = new Writer ();
ArrayList <Integer> [] g = new ArrayList [70010];
int [] mn = new int [70010];
int [] mx = new int [70010];
int [] par = new int [70010];
int [] dep = new int [70010];
int [] sub = new int [70010];
int [] l = new int [70010];
int [] r = new int [70010];
int [] al = new int [70010];
int [] ar = new int [70010];
boolean [] good = new boolean [70010];
boolean [] vis = new boolean [70010];
ArrayList <Integer> aux[] = new ArrayList [70010];
int ans[] = new int [70010];
void dfs(int x, int p) {
sub[x] = 1;
par[x] = p;
for(int e : g[x]) {
int y = l[e] ^ r[e] ^ x;
if(e != p) {
dep[y] = 1 + dep[x];
dfs(y, e);
sub[x] += sub[y];
}
}
}
void putMin(int p, int q, int val) {
while(dep[p] > dep[q]) {
int tmp = p;
p = q;
q = tmp;
}
while(dep[p] < dep[q]) {
int e = par[q];
mn[e] = Math.min(mn[e], val);
q ^= l[e] ^ r[e];
}
while(p != q) {
int e1 = par[p];
int e2 = par[q];
mn[e1] = Math.min(mn[e1], val);
mn[e2] = Math.min(mn[e2], val);
p ^= l[e1] ^ r[e1];
q ^= l[e2] ^ r[e2];
}
return ;
}
void putMax(int p, int q, int val) {
while(dep[p] > dep[q]) {
int tmp = p;
p = q;
q = tmp;
}
while(dep[p] < dep[q]) {
int e = par[q];
mx[e] = Math.max(mx[e], val);
q ^= l[e] ^ r[e];
}
while(p != q) {
int e1 = par[p];
int e2 = par[q];
mx[e1] = Math.max(mx[e1], val);
mx[e2] = Math.max(mx[e2], val);
p ^= l[e1] ^ r[e1];
q ^= l[e2] ^ r[e2];
}
return ;
}
void normal_assign(int x) {
vis[x] = true;
for(int e : aux[x]) {
int y = al[e] ^ ar[e] ^ x;
if(!vis[y]) {
ans[e] = y;
normal_assign(y);
}
}
}
int [] anc = new int [70010];
int [] rev = new int [70010];
int [] col = new int [70010];
boolean found;
void cycle(int x, int p) {
col[x] = 1;
anc[x] = p;
for(int e : aux[x]) {
int y = al[e] ^ ar[e] ^ x;
if(col[y] == 0) {
cycle(y, e);
} else if (e != p && col[y] == 1 && !found) {
int cur = x;
while(cur != y) {
int pe = anc[cur];
ans[pe] = cur;
good[cur] = true;
cur ^= al[pe] ^ ar[pe];
}
good[y] = true;
ans[e] = y;
found = true;
}
}
col[x] = -1;
}
void solve () {
int n = in.nextInt();
Arrays.fill(ans, -1);
for(int i = 0; i <= n; i++) {
g[i] = new ArrayList <> ();
mn[i] = Integer.MAX_VALUE;
mx[i] = Integer.MIN_VALUE;
}
for(int i = 1; i < n; i++) {
l[i] = in.nextInt();
r[i] = in.nextInt();
g[l[i]].add(i);
g[r[i]].add(i);
}
dfs(1, 0);
TreeMap <Integer, Integer> t = new TreeMap <> ();
int qr = in.nextInt();
for(int i = 1; i <= qr; i++) {
char c = in.next().charAt(0);
int x = in.nextInt();
int y = in.nextInt();
int val = in.nextInt();
if(c == 'M') {
putMin(x, y, val);
} else {
putMax(x, y, val);
}
t.put(val, i);
rev[i] = val;
}
for(int i = 1; i <= qr; i++) {
aux[i] = new ArrayList <> ();
}
for(int i = 1; i < n; i++) {
if(mx[i] == Integer.MIN_VALUE) {
good[t.get(mn[i])] = true;
ans[i] = t.get(mn[i]);
} else if (mn[i] == Integer.MAX_VALUE) {
good[t.get(mx[i])] = true;
ans[i] = t.get(mx[i]);
} else {
al[i] = t.get(mx[i]);
ar[i] = t.get(mn[i]);
aux[al[i]].add(i);
aux[ar[i]].add(i);
// System.out.println(al[i] + " " + ar[i] + " " + i);
}
}
for(int i = 1; i <= qr; i++) {
if(col[i] == 0) {
found = false;
cycle(i, 0);
}
}
for(int i = 1; i <= qr; i++) {
if(good[i] && !vis[i]) {
normal_assign(i);
}
}
for(int i = 1; i < n; i++) {
int val;
if(ans[i] == -1) val = 0;
else val = rev[ans[i]];
out.writeln(l[i] + " " + r[i] + " " + val);
}
out.flush();
}
}
class Reader {
private StringTokenizer a;
private BufferedReader b;
Reader () {
a = null;
try {
b = new BufferedReader (new InputStreamReader (System.in)); // for file IO, replace this with new FileReader ("in.txt")
} catch (Exception e) {
e.printStackTrace();
}
}
public String next () {
while(a == null || !a.hasMoreTokens()) {
try {
a = new StringTokenizer (b.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return a.nextToken();
}
public int nextInt() {
return Integer.parseInt(this.next());
}
public long nextLong () {
return Long.parseLong(this.next());
}
public double nextDouble () {
return Double.parseDouble(this.next());
}
public String nextLine() {
try {
return b.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return "";
}
}
class Writer {
private PrintWriter a;
private StringBuffer b;
Writer () {
try {
a = new PrintWriter (System.out); // for file IO, replace this with new FileWriter ("out.txt")
} catch (Exception e) {
e.printStackTrace();
}
b = new StringBuffer ("");
}
public void write (Object s) {
b.append(s);
}
public void writeln(Object s) {
b.append(s).append('\n');
}
public void flush () {
a.print(b);
a.flush();
a.close();
}
}
class Pair implements Comparator <Pair> {
int first;
int second;
Pair (int a, int b) {
this.first = a;
this.second = b;
}
Pair (Pair a) {
this.first = a.first;
this.second = a.second;
}
Pair () {}
public String toString () {
return "[" + first + ", " + second + "]";
}
public int compare (Pair a, Pair b) {
if(a.first == b.first) {
return a.second - b.second;
} else {
return a.first - b.first;
}
}
}