Submission #117091

#	Time	Username	Problem	Language	Result	Execution time	Memory
117091		Bruteforceman	Min-max tree (BOI18_minmaxtree)	Java	0 / 100	96 ms	9972 KiB

minmaxtree

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];

    void cycle(int x, int p) {
        vis[x] = true;
        anc[x] = p;
        for(int e : aux[x]) {
            int y = al[e] ^ ar[e] ^ x;
            if(!vis[y]) {
                cycle(y, e);
            } else if (e != p) {
                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;
            }
        }
    } 

    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]);
            }
        }
        for(int i = 1; i <= qr; i++) {
            if(!vis[i]) {
                cycle(i, 0);
            }
        }
        Arrays.fill(vis, false);
        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 FileReader ("minmaxtree.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 ("minmaxtree.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;
        }
    }
}

Compilation message (stderr)

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

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42