Submission #343380

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
343380	2021-01-03T20:03:36 Z	apostoldaniel854	Shymbulak (IZhO14_shymbulak)	C++14	Compilation error	0 ms	0 KB

shymbulak

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

/**
- we have a single cycle in this graph
- we calculate the maximum depth and its count in every tree spanning from the cycle
- we use a segmentree on a cyclic vector (we will double it)
- now we solve independently for every tree spaning from the cycle
**/

const int MAX_N = 2e5;
vector <int> cycle;
int state[1 + MAX_N];
bool fixed[1 + MAX_N];
void dfs_cycle (int node, int par) {
    state[node] = 1;
    v.pb (node);
    for (int vec : gr[node])
        if (vec != par) {
            if (state[vec] == 0)
                dfs_cycle (vec, node);
            else if (state[vec] == 1) {
                while (v.back () != vec) {
                    cycle.pb (v.back ());
                    v.pop_back ();
                }
                cycle.pb (vec);
            }
        }
    v.pop_back ();
    state[node] = 2;
}


struct Node {
    int value;
    int cnt;
};

Node max_depth[1 + MAX_N];
Node ans;

Node join (Node l, Node r) {
    Node x;
    x = l;
    if (x.value == r.value)
        x.cnt += r.cnt;
    else if (x.value < r.value)
        x = r;
    return x;
}

void dfs_depth (int node, int par) {
    max_depth[node] = {0, 1};
    for (int son : gr[node])
        if (son != par && not fixed[son]) {
            dfs_depth (son, node);
            upd_ans (max_depth[node], {max_depth[son].value + 1, max_depth[son].cnt});
            upd_ans (ans, {max_depth[node].value + max_depth[son].value + 1, max_depth[node].cnt * max_depth[son].cnt});
        }
}
struct LazySegTree {
    vector <Node> seg;
    vector <int> lazy;
    int n;
    LazySegTree (int n) {
        this->n = n;
        seg.resize (1 + 4 * n);
        lazy.resize (1 + 4 * n);
    }
    void push (int node) {
        if (lazy[node]) {
            int left_node = node * 2, right_node = node * 2 + 1;
            seg[left_node].value += lazy[node];
            seg[right_node].value += lazy[node];
            lazy[left_node] += lazy[node];
            lazy[right_node] += lazy[node];
            lazy[node] = 0;
        }
    }
    void build (int node, int lb, int rb, vector <pair <int, int>> &v) {
        if (lb == rb) {
            seg[node] = {v[lb - 1].first + lb - 1, v[lb - 1].second};
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        build (left_node, lb, mid, v);
        build (right_node, mid + 1, v);
        seg[node] = join (seg[left_node], seg[right_node]);
    }
    void update (int node, int lb, int rb, int q_left, int q_right, int to_add) {
        if (q_left <= lb && rb <= q_right) {
            seg[node].value += to_add;
            lazy[node] += to_add;
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        push (node);
        if (q_left <= mid)
            update (left_node, lb, mid, q_left, q_right, to_add);
        if (q_right >= mid + 1)
            update (right_node, mid + 1, rb, q_left, q_right, to_add);
        seg[node] = join (seg[left_node], seg[right_node]);
    }
    Node query (int node, int lb, int rb, int q_left, int q_right) {
        if (q_left <= lb && rb <= q_right) 
            return seg[node];
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        push (node);
        Node ans = {0, 0};
        if (q_left <= mid)
            ans = join (ans, query (left_node, lb, mid, q_left, q_right));
        if (q_right >= mid + 1)
            ans = join (ans, query (right_node, mid + 1, rb, q_left, q_right));
        return ans;
    }
};

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].pb (y);
        gr[y].pb (x);
    }
    dfs_cycle (1, 0);
    for (int x : cycle)
        fixed[x] = true;
    for (int x : cycle) 
        dfs_depths (x, 0);
    vector <int> elements;
    for (int x : cycle) 
        elements.pb (max_depth[x]);
    for (int x : cycle) 
        elements.pb (max_depth[x]);
    int m = cycle.size ();
    int sz = elements.size ();
    LazySegTree helper (sz);
    helper.build (1, 1, sz, elements);
    for (int i = 1; i <= m; i++) {
        Node l = helper.query (1, 1, sz, i);
    }
    return 0;
}

Compilation message

shymbulak.cpp: In function 'void dfs_cycle(int, int)':
shymbulak.cpp:22:5: error: 'v' was not declared in this scope
   22 |     v.pb (node);
      |     ^
shymbulak.cpp:23:20: error: 'gr' was not declared in this scope
   23 |     for (int vec : gr[node])
      |                    ^~
shymbulak.cpp: In function 'void dfs_depth(int, int)':
shymbulak.cpp:60:20: error: 'gr' was not declared in this scope
   60 |     for (int son : gr[node])
      |                    ^~
shymbulak.cpp:61:31: error: reference to 'fixed' is ambiguous
   61 |         if (son != par && not fixed[son]) {
      |                               ^~~~~
In file included from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from shymbulak.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1048:3: note: candidates are: 'std::ios_base& std::fixed(std::ios_base&)'
 1048 |   fixed(ios_base& __base)
      |   ^~~~~
shymbulak.cpp:19:6: note:                 'bool fixed [200001]'
   19 | bool fixed[1 + MAX_N];
      |      ^~~~~
shymbulak.cpp:63:13: error: 'upd_ans' was not declared in this scope
   63 |             upd_ans (max_depth[node], {max_depth[son].value + 1, max_depth[son].cnt});
      |             ^~~~~~~
shymbulak.cpp: In member function 'void LazySegTree::build(int, int, int, std::vector<std::pair<int, int> >&)':
shymbulak.cpp:93:38: error: no matching function for call to 'LazySegTree::build(int&, int, std::vector<std::pair<int, int> >&)'
   93 |         build (right_node, mid + 1, v);
      |                                      ^
shymbulak.cpp:86:10: note: candidate: 'void LazySegTree::build(int, int, int, std::vector<std::pair<int, int> >&)'
   86 |     void build (int node, int lb, int rb, vector <pair <int, int>> &v) {
      |          ^~~~~
shymbulak.cpp:86:10: note:   candidate expects 4 arguments, 3 provided
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:132:9: error: 'gr' was not declared in this scope
  132 |         gr[x].pb (y);
      |         ^~
shymbulak.cpp:137:9: error: reference to 'fixed' is ambiguous
  137 |         fixed[x] = true;
      |         ^~~~~
In file included from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from shymbulak.cpp:1:
/usr/include/c++/9/bits/ios_base.h:1048:3: note: candidates are: 'std::ios_base& std::fixed(std::ios_base&)'
 1048 |   fixed(ios_base& __base)
      |   ^~~~~
shymbulak.cpp:19:6: note:                 'bool fixed [200001]'
   19 | bool fixed[1 + MAX_N];
      |      ^~~~~
shymbulak.cpp:139:9: error: 'dfs_depths' was not declared in this scope; did you mean 'dfs_depth'?
  139 |         dfs_depths (x, 0);
      |         ^~~~~~~~~~
      |         dfs_depth
shymbulak.cpp:142:34: error: no matching function for call to 'std::vector<int>::push_back(Node&)'
  142 |         elements.pb (max_depth[x]);
      |                                  ^
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from shymbulak.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:1184:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1184 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1184:35: note:   no known conversion for argument 1 from 'Node' to 'const value_type&' {aka 'const int&'}
 1184 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_vector.h:1200:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1200 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1200:30: note:   no known conversion for argument 1 from 'Node' to 'std::vector<int>::value_type&&' {aka 'int&&'}
 1200 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
shymbulak.cpp:144:34: error: no matching function for call to 'std::vector<int>::push_back(Node&)'
  144 |         elements.pb (max_depth[x]);
      |                                  ^
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from shymbulak.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:1184:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1184 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1184:35: note:   no known conversion for argument 1 from 'Node' to 'const value_type&' {aka 'const int&'}
 1184 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_vector.h:1200:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]'
 1200 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1200:30: note:   no known conversion for argument 1 from 'Node' to 'std::vector<int>::value_type&&' {aka 'int&&'}
 1200 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
shymbulak.cpp:148:29: error: cannot convert 'std::vector<int>' to 'std::vector<std::pair<int, int> >&'
  148 |     helper.build (1, 1, sz, elements);
      |                             ^~~~~~~~
      |                             |
      |                             std::vector<int>
shymbulak.cpp:86:69: note:   initializing argument 4 of 'void LazySegTree::build(int, int, int, std::vector<std::pair<int, int> >&)'
   86 |     void build (int node, int lb, int rb, vector <pair <int, int>> &v) {
      |                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~^
shymbulak.cpp:150:43: error: no matching function for call to 'LazySegTree::query(int, int, int&, int&)'
  150 |         Node l = helper.query (1, 1, sz, i);
      |                                           ^
shymbulak.cpp:110:10: note: candidate: 'Node LazySegTree::query(int, int, int, int, int)'
  110 |     Node query (int node, int lb, int rb, int q_left, int q_right) {
      |          ^~~~~
shymbulak.cpp:110:10: note:   candidate expects 5 arguments, 4 provided
shymbulak.cpp:150:14: warning: unused variable 'l' [-Wunused-variable]
  150 |         Node l = helper.query (1, 1, sz, i);
      |              ^