oj.uz

Submission #333822

# Submission time Handle Problem Language Result Execution time Memory
333822 2020-12-07T20:34:18 Z 12tqian Mergers (JOI19_mergers) C++17
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>

int main() {
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> s(n);
    for (int i = 0; i < n; i++) 
        cin >> s[i], s[i]--;
    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }
    vector<int> tot(n);
    for (int x : s)
        tot[x]++;
    vector<multiset<int>> store(n);
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    vector<int> bad(n);
    function<void(int, int)> combine = [&](int src, int par) {
        if (tot[s[src]] != 1)
            store[id[src]].insert(s[src]);
        for (int nxt : adj[src]){ 
            if (nxt == par)
                continue;
            combine(nxt, src);
            if ((int) store[id[src]].size() < (int) store[id[nxt]].size()) 
                swap(id[src], id[nxt]);
            for (int x : store[id[nxt]]) {
                store[id[src]].insert(x);
                if (store[id[src]].count(x) == tot[x])
                    store[id[src]].erase(x);
            }
        }
        if ((int) store[id[src]].size() == 0 && src != 0) 
            bad[src] = 1;
    };
    combine(0, -1);
    int amt = 0;
    for (int i = 1; i < n; i++)
        amt += bad[i];
    int leaves = 0;
    function<int(int, int)> dfs_sub = [&](int src, int par) -> int {
        int sub = bad[src];
        for (int nxt : adj[src]) {
            if (nxt == par)
                continue;
            sub += dfs_sub(nxt, src);
        }
        if (sub == 1 && bad[src]) 
            leaves++;
        else if (sub == amt && bad[src])
            leaves++;
        return sub;
    };
    dfs_sub(0, -1);
    int ans = (leaves + 1) / 2;
    cout << ans << '\n';
    return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:4:5: error: 'ios_base' has not been declared
    4 |     ios_base::sync_with_stdio(0);
      |     ^~~~~~~~
mergers.cpp:6:5: error: 'cin' was not declared in this scope; did you mean 'std::cin'?
    6 |     cin >> n >> k;
      |     ^~~
      |     std::cin
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:75,
                 from mergers.cpp:1:
/usr/include/c++/9/iostream:60:18: note: 'std::cin' declared here
   60 |   extern istream cin;  /// Linked to standard input
      |                  ^~~
mergers.cpp:7:5: error: 'vector' was not declared in this scope
    7 |     vector<vector<int>> adj(n);
      |     ^~~~~~
mergers.cpp:7:5: note: suggested alternatives:
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/functional:62,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from mergers.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:386:11: note:   'std::vector'
  386 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
In file included from /usr/include/c++/9/functional:62,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from mergers.cpp:1:
/usr/include/c++/9/vector:90:13: note:   'std::pmr::vector'
   90 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
mergers.cpp:7:19: error: expected primary-expression before 'int'
    7 |     vector<vector<int>> adj(n);
      |                   ^~~
mergers.cpp:11:9: error: 'adj' was not declared in this scope
   11 |         adj[u].push_back(v);
      |         ^~~
mergers.cpp:14:12: error: expected primary-expression before 'int'
   14 |     vector<int> s(n);
      |            ^~~
mergers.cpp:16:16: error: 's' was not declared in this scope
   16 |         cin >> s[i], s[i]--;
      |                ^
mergers.cpp:18:9: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
   18 |         cout << 0 << '\n';
      |         ^~~~
      |         std::cout
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:75,
                 from mergers.cpp:1:
/usr/include/c++/9/iostream:61:18: note: 'std::cout' declared here
   61 |   extern ostream cout;  /// Linked to standard output
      |                  ^~~~
mergers.cpp:21:12: error: expected primary-expression before 'int'
   21 |     vector<int> tot(n);
      |            ^~~
mergers.cpp:22:18: error: 's' was not declared in this scope
   22 |     for (int x : s)
      |                  ^
mergers.cpp:23:9: error: 'tot' was not declared in this scope
   23 |         tot[x]++;
      |         ^~~
mergers.cpp:24:12: error: 'multiset' was not declared in this scope
   24 |     vector<multiset<int>> store(n);
      |            ^~~~~~~~
mergers.cpp:24:12: note: suggested alternatives:
In file included from /usr/include/c++/9/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
                 from mergers.cpp:1:
/usr/include/c++/9/bits/stl_set.h:70:11: note:   'std::multiset'
   70 |     class multiset;
      |           ^~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
                 from mergers.cpp:1:
/usr/include/c++/9/set:84:13: note:   'std::pmr::multiset'
   84 |       using multiset = std::multiset<_Key, _Cmp, polymorphic_allocator<_Key>>;
      |             ^~~~~~~~
mergers.cpp:24:21: error: expected primary-expression before 'int'
   24 |     vector<multiset<int>> store(n);
      |                     ^~~
mergers.cpp:25:12: error: expected primary-expression before 'int'
   25 |     vector<int> id(n);
      |            ^~~
mergers.cpp:26:10: error: 'id' was not declared in this scope
   26 |     iota(id.begin(), id.end(), 0);
      |          ^~
mergers.cpp:26:5: error: 'iota' was not declared in this scope; did you mean 'std::iota'?
   26 |     iota(id.begin(), id.end(), 0);
      |     ^~~~
      |     std::iota
In file included from /usr/include/c++/9/numeric:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:84,
                 from mergers.cpp:1:
/usr/include/c++/9/bits/stl_numeric.h:87:5: note: 'std::iota' declared here
   87 |     iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
      |     ^~~~
mergers.cpp:27:12: error: expected primary-expression before 'int'
   27 |     vector<int> bad(n);
      |            ^~~
mergers.cpp:28:5: error: 'function' was not declared in this scope; did you mean 'std::function'?
   28 |     function<void(int, int)> combine = [&](int src, int par) {
      |     ^~~~~~~~
      |     std::function
In file included from /usr/include/c++/9/functional:59,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from mergers.cpp:1:
/usr/include/c++/9/bits/std_function.h:128:11: note: 'std::function' declared here
  128 |     class function;
      |           ^~~~~~~~
mergers.cpp:28:27: error: expression list treated as compound expression in functional cast [-fpermissive]
   28 |     function<void(int, int)> combine = [&](int src, int par) {
      |                           ^
mergers.cpp:28:14: error: expected primary-expression before 'void'
   28 |     function<void(int, int)> combine = [&](int src, int par) {
      |              ^~~~
mergers.cpp:46:5: error: 'combine' was not declared in this scope
   46 |     combine(0, -1);
      |     ^~~~~~~
mergers.cpp:49:16: error: 'bad' was not declared in this scope
   49 |         amt += bad[i];
      |                ^~~
mergers.cpp:51:26: error: expression list treated as compound expression in functional cast [-fpermissive]
   51 |     function<int(int, int)> dfs_sub = [&](int src, int par) -> int {
      |                          ^
mergers.cpp:51:14: error: expected primary-expression before 'int'
   51 |     function<int(int, int)> dfs_sub = [&](int src, int par) -> int {
      |              ^~~
mergers.cpp:64:5: error: 'dfs_sub' was not declared in this scope
   64 |     dfs_sub(0, -1);
      |     ^~~~~~~
mergers.cpp:66:5: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
   66 |     cout << ans << '\n';
      |     ^~~~
      |     std::cout
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:75,
                 from mergers.cpp:1:
/usr/include/c++/9/iostream:61:18: note: 'std::cout' declared here
   61 |   extern ostream cout;  /// Linked to standard output
      |                  ^~~~