답안 #343426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343426	2021-01-03T23:19:35 Z	ijxjdjd	Min-max tree (BOI18_minmaxtree)	C++14	컴파일 오류	0 ms	0 KB

minmaxtree

int deg[MAXN];
unordered_map<int, int> condense;
int rev[MAXN];
pi merge(pi x, pi y) {
    if (minc[x.first].size() < minc[y.first].size()) {
        swap(x.first, y.first);
    }
    if (maxc[x.second].size() < minc[y.second].size()) {
        swap(x.second, y.second);
    }
    for (int i : minc[y.first]) {
        if (minc[x.first].count(i)) {
            minc[x.first].erase(i);
        }
        else {
            minc[x.first].insert(i);
        }
    }
    for (int i : maxc[y.second]) {
        if (maxc[x.second].count(i)) {
            maxc[x.second].erase(i);
        }
        else {
            maxc[x.second].insert(i);
        }
    }
    maxc[x.second].erase(i);
    return x;
}
pi root(int n, int p) {
    pi cur = {n, n};
    par[n] = p;
    for (int e : adj[n]) {
        if (e != p) {
            cur = merge(cur, root(e, n));
        }
    }
    if (minc[cur.first].size() > 0) {
        int z = *(minc[cur.first].rbegin());
        if (!condense.count(z)) {
            rev[condense.size()] = z;
            condense[z] = condense.size();
        }
        color[condense[z]].push_back(n);
        to[n].push_back(condense[z]);
    }
    if (maxc[cur.second].size() > 0) {
        int z = *(maxc[cur.second].begin());
        if (!condense.count(z)) {
            rev[condense.size()] = z;
            condense[z] = condense.size();
        }
        color[condense[z]].push_back(n);
        to[n].push_back(condense[z]);
    }
    return cur;
}
int main()
{
//    freopen("input.in", "r", stdin);
    int N;
    cin >> N;
    FR(i, N-1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        ans[i] = -1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    ans[N-1] = -1;
    int K;
    cin >> K;
    FR(i, K) {
        char c;
        int x, y, z;
        cin >> c;
        cin >> x >> y >> z;
        x--, y--;
        if (x != y) {
            if (c == 'm') {
                minc[x].insert(z);
                minc[y].insert(z);
            }
            else {
                maxc[x].insert(z);
                maxc[y].insert(z);
            }
        }
    }
    root(0, 0);
    queue<int> deq;
    unordered_set<int> unvis;
    for (int i = 0; i < condense.size(); i++) {
        deg[i] = color[i].size();
        if (deg[i] == 1) {
            deq.push(i);
        }
        else {
            unvis.insert(i);
        }
    }
    while (unvis.size() > 0) {

        while (deq.size() > 0) {
            int next = deq.front(); deq.pop();
            for (int j : color[next]) {
                if (!visited[j]) {
                    visited[j] = true;
                    ans[j] = rev[next];
                    for (int e : to[j]) {
                        deg[e]--;
                        if (deg[e] == 1 && unvis.count(e)) {
                            deq.push(e);
                            unvis.erase(e);
                        }
                    }
                    break;
                }
            }
        }
        if (unvis.size() > 0) {
            int j = *unvis.begin();
            unvis.erase(j);
            deq.push(j);
        }
    }
    for (int i = 1; i < N; i++) {
        if (ans[i] == -1) {
            if (to[i].size() > 0) {
                ans[i] = rev[to[i][0]];
            }
            else {
                ans[i] = 1;
            }
        }
        cout << par[i]+1 << " " << i+1 << " " << ans[i] << '\n';
    }
    return 0;
}

Compilation message

minmaxtree.cpp:2:9: error: 'MAXN' was not declared in this scope
    2 | int deg[MAXN];
      |         ^~~~
minmaxtree.cpp:3:1: error: 'unordered_map' does not name a type
    3 | unordered_map<int, int> condense;
      | ^~~~~~~~~~~~~
minmaxtree.cpp:4:9: error: 'MAXN' was not declared in this scope
    4 | int rev[MAXN];
      |         ^~~~
minmaxtree.cpp:5:1: error: 'pi' does not name a type
    5 | pi merge(pi x, pi y) {
      | ^~
minmaxtree.cpp:31:1: error: 'pi' does not name a type
   31 | pi root(int n, int p) {
      | ^~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:63:5: error: 'cin' was not declared in this scope
   63 |     cin >> N;
      |     ^~~
minmaxtree.cpp:64:8: error: 'i' was not declared in this scope
   64 |     FR(i, N-1) {
      |        ^
minmaxtree.cpp:64:5: error: 'FR' was not declared in this scope
   64 |     FR(i, N-1) {
      |     ^~
minmaxtree.cpp:72:5: error: 'ans' was not declared in this scope
   72 |     ans[N-1] = -1;
      |     ^~~
minmaxtree.cpp:92:5: error: 'root' was not declared in this scope
   92 |     root(0, 0);
      |     ^~~~
minmaxtree.cpp:93:5: error: 'queue' was not declared in this scope
   93 |     queue<int> deq;
      |     ^~~~~
minmaxtree.cpp:93:11: error: expected primary-expression before 'int'
   93 |     queue<int> deq;
      |           ^~~
minmaxtree.cpp:94:5: error: 'unordered_set' was not declared in this scope
   94 |     unordered_set<int> unvis;
      |     ^~~~~~~~~~~~~
minmaxtree.cpp:94:19: error: expected primary-expression before 'int'
   94 |     unordered_set<int> unvis;
      |                   ^~~
minmaxtree.cpp:95:25: error: 'condense' was not declared in this scope
   95 |     for (int i = 0; i < condense.size(); i++) {
      |                         ^~~~~~~~
minmaxtree.cpp:96:9: error: 'deg' was not declared in this scope
   96 |         deg[i] = color[i].size();
      |         ^~~
minmaxtree.cpp:96:18: error: 'color' was not declared in this scope
   96 |         deg[i] = color[i].size();
      |                  ^~~~~
minmaxtree.cpp:98:13: error: 'deq' was not declared in this scope
   98 |             deq.push(i);
      |             ^~~
minmaxtree.cpp:101:13: error: 'unvis' was not declared in this scope
  101 |             unvis.insert(i);
      |             ^~~~~
minmaxtree.cpp:104:12: error: 'unvis' was not declared in this scope
  104 |     while (unvis.size() > 0) {
      |            ^~~~~
minmaxtree.cpp:106:16: error: 'deq' was not declared in this scope
  106 |         while (deq.size() > 0) {
      |                ^~~
minmaxtree.cpp:108:26: error: 'color' was not declared in this scope
  108 |             for (int j : color[next]) {
      |                          ^~~~~
minmaxtree.cpp:109:22: error: 'visited' was not declared in this scope
  109 |                 if (!visited[j]) {
      |                      ^~~~~~~
minmaxtree.cpp:111:30: error: 'rev' was not declared in this scope
  111 |                     ans[j] = rev[next];
      |                              ^~~
minmaxtree.cpp:112:34: error: 'to' was not declared in this scope
  112 |                     for (int e : to[j]) {
      |                                  ^~
minmaxtree.cpp:113:25: error: 'deg' was not declared in this scope
  113 |                         deg[e]--;
      |                         ^~~
minmaxtree.cpp:126:13: error: 'deq' was not declared in this scope
  126 |             deq.push(j);
      |             ^~~
minmaxtree.cpp:131:17: error: 'to' was not declared in this scope
  131 |             if (to[i].size() > 0) {
      |                 ^~
minmaxtree.cpp:132:26: error: 'rev' was not declared in this scope
  132 |                 ans[i] = rev[to[i][0]];
      |                          ^~~
minmaxtree.cpp:138:9: error: 'cout' was not declared in this scope
  138 |         cout << par[i]+1 << " " << i+1 << " " << ans[i] << '\n';
      |         ^~~~
minmaxtree.cpp:138:17: error: 'par' was not declared in this scope
  138 |         cout << par[i]+1 << " " << i+1 << " " << ans[i] << '\n';
      |                 ^~~