답안 #117094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117094	2019-06-14T19:13:28 Z	Bruteforceman	Min-max tree (BOI18_minmaxtree)	C++11	컴파일 오류	0 ms	0 KB

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

Compilation message

minmaxtree.cpp:2:1: error: 'import' does not name a type; did you mean 'short'?
 import java.util.*;
 ^~~~~~
 short
minmaxtree.cpp:3:1: error: 'import' does not name a type; did you mean 'short'?
 import java.io.*;
 ^~~~~~
 short
minmaxtree.cpp:6:12: error: expected ':' before 'static'
     public static void main(String [] args) {
            ^~~~~~
minmaxtree.cpp:6:29: error: 'String' has not been declared
     public static void main(String [] args) {
                             ^~~~~~
minmaxtree.cpp:6:39: error: expected ',' or '...' before 'args'
     public static void main(String [] args) {
                                       ^~~~
minmaxtree.cpp:10:2: error: expected ';' after class definition
 }
  ^
  ;
minmaxtree.cpp: In static member function 'static void MinMaxTree::main(int*)':
minmaxtree.cpp:7:9: error: 'Solver' was not declared in this scope
         Solver s = new Solver();
         ^~~~~~
minmaxtree.cpp:8:9: error: 's' was not declared in this scope
         s.solve();
         ^
minmaxtree.cpp: At global scope:
minmaxtree.cpp:13:5: error: 'Reader' does not name a type
     Reader in = new Reader ();
     ^~~~~~
minmaxtree.cpp:14:5: error: 'Writer' does not name a type
     Writer out = new Writer ();
     ^~~~~~
minmaxtree.cpp:15:5: error: 'ArrayList' does not name a type
     ArrayList <Integer> [] g = new ArrayList [70010];
     ^~~~~~~~~
minmaxtree.cpp:16:9: error: expected unqualified-id before '[' token
     int [] mn = new int [70010];
         ^
minmaxtree.cpp:17:9: error: expected unqualified-id before '[' token
     int [] mx = new int [70010];
         ^
minmaxtree.cpp:18:9: error: expected unqualified-id before '[' token
     int [] par = new int [70010];
         ^
minmaxtree.cpp:19:9: error: expected unqualified-id before '[' token
     int [] dep = new int [70010];
         ^
minmaxtree.cpp:20:9: error: expected unqualified-id before '[' token
     int [] sub = new int [70010];
         ^
minmaxtree.cpp:22:9: error: expected unqualified-id before '[' token
     int [] l = new int [70010];
         ^
minmaxtree.cpp:23:9: error: expected unqualified-id before '[' token
     int [] r = new int [70010];
         ^
minmaxtree.cpp:25:9: error: expected unqualified-id before '[' token
     int [] al = new int [70010];
         ^
minmaxtree.cpp:26:9: error: expected unqualified-id before '[' token
     int [] ar = new int [70010];
         ^
minmaxtree.cpp:27:5: error: 'boolean' does not name a type; did you mean 'bool'?
     boolean [] good = new boolean [70010];
     ^~~~~~~
     bool
minmaxtree.cpp:28:5: error: 'boolean' does not name a type; did you mean 'bool'?
     boolean [] vis = new boolean [70010];
     ^~~~~~~
     bool
minmaxtree.cpp:30:5: error: 'ArrayList' does not name a type
     ArrayList <Integer> aux[] = new ArrayList [70010];
     ^~~~~~~~~
minmaxtree.cpp:98:9: error: expected unqualified-id before '[' token
     int [] anc = new int [70010];
         ^
minmaxtree.cpp:99:9: error: expected unqualified-id before '[' token
     int [] rev = new int [70010];
         ^
minmaxtree.cpp:100:9: error: expected unqualified-id before '[' token
     int [] col = new int [70010];
         ^
minmaxtree.cpp:101:5: error: 'boolean' does not name a type; did you mean 'bool'?
     boolean found;
     ^~~~~~~
     bool
minmaxtree.cpp:31:31: error: flexible array member 'Solver::ans' in an otherwise empty 'class Solver'
     int ans[] = new int [70010];
                               ^
minmaxtree.cpp:194:2: error: expected ';' after class definition
 }
  ^
  ;
minmaxtree.cpp:31:31: error: initializer for flexible array member 'int Solver::ans []'
     int ans[] = new int [70010];
                               ^
minmaxtree.cpp: In member function 'void Solver::dfs(int, int)':
minmaxtree.cpp:34:9: error: 'sub' was not declared in this scope
         sub[x] = 1;
         ^~~
minmaxtree.cpp:35:9: error: 'par' was not declared in this scope
         par[x] = p;
         ^~~
minmaxtree.cpp:35:9: note: suggested alternative: 'char'
         par[x] = p;
         ^~~
         char
minmaxtree.cpp:36:21: error: 'g' was not declared in this scope
         for(int e : g[x]) {
                     ^
minmaxtree.cpp:37:21: error: 'l' was not declared in this scope
             int y = l[e] ^ r[e] ^ x;  
                     ^
minmaxtree.cpp:37:28: error: 'r' was not declared in this scope
             int y = l[e] ^ r[e] ^ x;  
                            ^
minmaxtree.cpp:39:17: error: 'dep' was not declared in this scope
                 dep[y] = 1 + dep[x];
                 ^~~
minmaxtree.cpp: In member function 'void Solver::putMin(int, int, int)':
minmaxtree.cpp:46:15: error: 'dep' was not declared in this scope
         while(dep[p] > dep[q]) {
               ^~~
minmaxtree.cpp:51:15: error: 'dep' was not declared in this scope
         while(dep[p] < dep[q]) {
               ^~~
minmaxtree.cpp:52:21: error: 'par' was not declared in this scope
             int e = par[q];
                     ^~~
minmaxtree.cpp:53:13: error: 'mn' was not declared in this scope
             mn[e] = Math.min(mn[e], val);
             ^~
minmaxtree.cpp:53:21: error: 'Math' was not declared in this scope
             mn[e] = Math.min(mn[e], val);
                     ^~~~
minmaxtree.cpp:54:18: error: 'l' was not declared in this scope
             q ^= l[e] ^ r[e];
                  ^
minmaxtree.cpp:54:25: error: 'r' was not declared in this scope
             q ^= l[e] ^ r[e];
                         ^
minmaxtree.cpp:57:22: error: 'par' was not declared in this scope
             int e1 = par[p];
                      ^~~
minmaxtree.cpp:59:13: error: 'mn' was not declared in this scope
             mn[e1] = Math.min(mn[e1], val);
             ^~
minmaxtree.cpp:59:22: error: 'Math' was not declared in this scope
             mn[e1] = Math.min(mn[e1], val);
                      ^~~~
minmaxtree.cpp:61:18: error: 'l' was not declared in this scope
             p ^= l[e1] ^ r[e1];
                  ^
minmaxtree.cpp:61:26: error: 'r' was not declared in this scope
             p ^= l[e1] ^ r[e1];
                          ^
minmaxtree.cpp: In member function 'void Solver::putMax(int, int, int)':
minmaxtree.cpp:67:15: error: 'dep' was not declared in this scope
         while(dep[p] > dep[q]) {
               ^~~
minmaxtree.cpp:72:15: error: 'dep' was not declared in this scope
         while(dep[p] < dep[q]) {
               ^~~
minmaxtree.cpp:73:21: error: 'par' was not declared in this scope
             int e = par[q];
                     ^~~
minmaxtree.cpp:74:13: error: 'mx' was not declared in this scope
             mx[e] = Math.max(mx[e], val);
             ^~
minmaxtree.cpp:74:21: error: 'Math' was not declared in this scope
             mx[e] = Math.max(mx[e], val);
                     ^~~~
minmaxtree.cpp:75:18: error: 'l' was not declared in this scope
             q ^= l[e] ^ r[e];
                  ^
minmaxtree.cpp:75:25: error: 'r' was not declared in this scope
             q ^= l[e] ^ r[e];
                         ^
minmaxtree.cpp:78:22: error: 'par' was not declared in this scope
             int e1 = par[p];
                      ^~~
minmaxtree.cpp:80:13: error: 'mx' was not declared in this scope
             mx[e1] = Math.max(mx[e1], val);
             ^~
minmaxtree.cpp:80:22: error: 'Math' was not declared in this scope
             mx[e1] = Math.max(mx[e1], val);
                      ^~~~
minmaxtree.cpp:82:18: error: 'l' was not declared in this scope
             p ^= l[e1] ^ r[e1];
                  ^
minmaxtree.cpp:82:26: error: 'r' was not declared in this scope
             p ^= l[e1] ^ r[e1];
                          ^
minmaxtree.cpp: In member function 'void Solver::normal_assign(int)':
minmaxtree.cpp:88:9: error: 'vis' was not declared in this scope
         vis[x] = true;
         ^~~
minmaxtree.cpp:88:9: note: suggested alternative: 'this'
         vis[x] = true;
         ^~~
         this
minmaxtree.cpp:89:21: error: 'aux' was not declared in this scope
         for(int e : aux[x]) {
                     ^~~
minmaxtree.cpp:89:21: note: suggested alternative: 'auto'
         for(int e : aux[x]) {
                     ^~~
                     auto
minmaxtree.cpp:90:21: error: 'al' was not declared in this scope
             int y = al[e] ^ ar[e] ^ x;
                     ^~
minmaxtree.cpp:90:29: error: 'ar' was not declared in this scope
             int y = al[e] ^ ar[e] ^ x;
                             ^~
minmaxtree.cpp: In member function 'void Solver::cycle(int, int)':
minmaxtree.cpp:104:9: error: 'col' was not declared in this scope
         col[x] = 1;
         ^~~
minmaxtree.cpp:104:9: note: suggested alternative: 'bool'
         col[x] = 1;
         ^~~
         bool
minmaxtree.cpp:105:9: error: 'anc' was not declared in this scope
         anc[x] = p;
         ^~~
minmaxtree.cpp:105:9: note: suggested alternative: 'ans'
         anc[x] = p;
         ^~~
         ans
minmaxtree.cpp:106:21: error: 'aux' was not declared in this scope
         for(int e : aux[x]) {
                     ^~~
minmaxtree.cpp:106:21: note: suggested alternative: 'auto'
         for(int e : aux[x]) {
                     ^~~
                     auto
minmaxtree.cpp:107:21: error: 'al' was not declared in this scope
             int y = al[e] ^ ar[e] ^ x;
                     ^~
minmaxtree.cpp:107:29: error: 'ar' was not declared in this scope
             int y = al[e] ^ ar[e] ^ x;
                             ^~
minmaxtree.cpp:110:50: error: 'found' was not declared in this scope
             } else if (e != p && col[y] == 1 && !found) {
                                                  ^~~~~
minmaxtree.cpp:115:21: error: 'good' was not declared in this scope
                     good[cur] = true;
                     ^~~~
minmaxtree.cpp:115:21: note: suggested alternative: 'bool'
                     good[cur] = true;
                     ^~~~
                     bool
minmaxtree.cpp:118:17: error: 'good' was not declared in this scope
                 good[y] = true;
                 ^~~~
minmaxtree.cpp:118:17: note: suggested alternative: 'bool'
                 good[y] = true;
                 ^~~~
                 bool
minmaxtree.cpp: In member function 'void Solver::solve()':
minmaxtree.cpp:127:17: error: 'in' was not declared in this scope
         int n = in.nextInt();
                 ^~
minmaxtree.cpp:127:17: note: suggested alternative: 'n'
         int n = in.nextInt();
                 ^~
                 n
minmaxtree.cpp:128:9: error: 'Arrays' was not declared in this scope
         Arrays.fill(ans, -1);
         ^~~~~~
minmaxtree.cpp:130:13: error: 'g' was not declared in this scope
             g[i] = new ArrayList <> ();
             ^
minmaxtree.cpp:130:24: error: 'ArrayList' does not name a type
             g[i] = new ArrayList <> ();
                        ^~~~~~~~~
minmaxtree.cpp:130:35: error: expected primary-expression before '>' token
             g[i] = new ArrayList <> ();
                                   ^
minmaxtree.cpp:130:38: error: expected primary-expression before ')' token
             g[i] = new ArrayList <> ();
                                      ^
minmaxtree.cpp:131:13: error: 'mn' was not declared in this scope
             mn[i] = Integer.MAX_VALUE;
             ^~
minmaxtree.cpp:131:13: note: suggested alternative: 'n'
             mn[i] = Integer.MAX_VALUE;
             ^~
             n
minmaxtree.cpp:131:21: error: 'Integer' was not declared in this scope
             mn[i] = Integer.MAX_VALUE;
                     ^~~~~~~
minmaxtree.cpp:132:13: error: 'mx' was not declared in this scope
             mx[i] = Integer.MIN_VALUE;
             ^~
minmaxtree.cpp:135:13: error: 'l' was not declared in this scope
             l[i] = in.nextInt();
             ^
minmaxtree.cpp:136:13: error: 'r' was not declared in this scope
             r[i] = in.nextInt();
             ^
minmaxtree.cpp:137:13: error: 'g' was not declared in this scope
             g[l[i]].add(i);
             ^
minmaxtree.cpp:142:9: error: 'TreeMap' was not declared in this scope
         TreeMap <Integer, Integer> t = new TreeMap <> ();
         ^~~~~~~
minmaxtree.cpp:142:18: error: 'Integer' was not declared in this scope
         TreeMap <Integer, Integer> t = new TreeMap <> ();
                  ^~~~~~~
minmaxtree.cpp:142:36: error: 't' was not declared in this scope
         TreeMap <Integer, Integer> t = new TreeMap <> ();
                                    ^
minmaxtree.cpp:142:44: error: 'TreeMap' does not name a type
         TreeMap <Integer, Integer> t = new TreeMap <> ();
                                            ^~~~~~~
minmaxtree.cpp:142:53: error: expected primary-expression before '>' token
         TreeMap <Integer, Integer> t = new TreeMap <> ();
                                                     ^
minmaxtree.cpp:142:56: error: expected primary-expression before ')' token
         TreeMap <Integer, Integer> t = new TreeMap <> ();
                                                        ^
minmaxtree.cpp:155:13: error: 'rev' was not declared in this scope
             rev[i] = val;
             ^~~
minmaxtree.cpp:158:13: error: 'aux' was not declared in this scope
             aux[i] = new ArrayList <> ();
             ^~~
minmaxtree.cpp:158:13: note: suggested alternative: 'auto'
             aux[i] = new ArrayList <> ();
             ^~~
             auto
minmaxtree.cpp:158:26: error: 'ArrayList' does not name a type
             aux[i] = new ArrayList <> ();
                          ^~~~~~~~~
minmaxtree.cpp:158:37: error: expected primary-expression before '>' token
             aux[i] = new ArrayList <> ();
                                     ^
minmaxtree.cpp:158:40: error: expected primary-expression before ')' token
             aux[i] = new ArrayList <> ();
                                        ^
minmaxtree.cpp:161:16: error: 'mx' was not declared in this scope
             if(mx[i] == Integer.MIN_VALUE) {
                ^~
minmaxtree.cpp:162:17: error: 'good' was not declared in this scope
                 good[t.get(mn[i])] = true;
                 ^~~~
minmaxtree.cpp:162:17: note: suggested alternative: 'bool'
                 good[t.get(mn[i])] = true;
                 ^~~~
                 bool
minmaxtree.cpp:162:28: error: 'mn' was not declared in this scope
                 good[t.get(mn[i])] = true;
                            ^~
minmaxtree.cpp:162:28: note: suggested alternative: 'n'
                 good[t.get(mn[i])] = true;
                            ^~
                            n
minmaxtree.cpp:164:24: error: 'mn' was not declared in this scope
             } else if (mn[i] == Integer.MAX_VALUE) {
                        ^~
minmaxtree.cpp:164:24: note: suggested alternative: 'n'
             } else if (mn[i] == Integer.MAX_VALUE) {
                        ^~
                        n
minmaxtree.cpp:165:17: error: 'good' was not declared in this scope
                 good[t.get(mx[i])] = true;
                 ^~~~
minmaxtree.cpp:165:17: note: suggested alternative: 'bool'
                 good[t.get(mx[i])] = true;
                 ^~~~
                 bool
minmaxtree.cpp:168:17: error: 'al' was not declared in this scope
                 al[i] = t.get(mx[i]);
                 ^~
minmaxtree.cpp:169:17: error: 'ar' was not declared in this scope
                 ar[i] = t.get(mn[i]);
                 ^~
minmaxtree.cpp:169:17: note: suggested alternative: 'qr'
                 ar[i] = t.get(mn[i]);
                 ^~
                 qr
minmaxtree.cpp:170:17: error: 'aux' was not declared in this scope
                 aux[al[i]].add(i);
                 ^~~
minmaxtree.cpp:170:17: note: suggested alternative: 'auto'
                 aux[al[i]].add(i);
                 ^~~
                 auto
minmaxtree.cpp:176:16: error: 'col' was not declared in this scope
             if(col[i] == 0) {
                ^~~
minmaxtree.cpp:176:16: note: suggested alternative: 'bool'
             if(col[i] == 0) {
                ^~~
                bool
minmaxtree.cpp:177:17: error: 'found' was not declared in this scope
                 found = false;
                 ^~~~~
minmaxtree.cpp:182:16: error: 'good' was not declared in this scope
             if(good[i] && !vis[i]) {
                ^~~~
minmaxtree.cpp:182:16: note: suggested alternative: 'bool'
             if(good[i] && !vis[i]) {
                ^~~~
                bool
minmaxtree.cpp:182:28: error: 'vis' was not declared in this scope
             if(good[i] && !vis[i]) {
                            ^~~
/var/loc