Submission #924070

#	Time	Username	Problem	Language	Result	Execution time	Memory
924070		danikoynov	Minerals (JOI19_minerals)	C++14	Compilation error	0 ms	0 KiB

minerals

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

int n, p[maxn];
ll w[maxn];

void input()
{
    cin >> n;
    for (int i = 2; i <= n; i ++)
        cin >> p[i];
    for (int i = 2; i <= n; i ++)
        cin >> w[i];
}

vector < pair < int, ll > > adj[maxn];

int tin[maxn], occ[2 * maxn], timer;
ll depth[maxn];

void traverse(int v)
{
    tin[v] = ++ timer;
    occ[timer] = v;
    for (pair < int, ll > nb : adj[v])
    {
        depth[nb.first] = depth[v] + nb.second;
        traverse(nb.first);
        occ[++ timer] = v;
    }
}

const int maxlog = 21;
int dp[maxlog][2 * maxn], lg[2 * maxn];

void sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        lg[i] = lg[i / 2] + 1;
        dp[0][i] = occ[i];
    }

    for (int j = 1; j < lg[timer]; j ++)
        for (int i = 1; i <= timer - (1 << j) + 1; i ++)
        {
            dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
            if (depth[dp[j - 1][i]] < depth[dp[j][i]])
                dp[j][i] = dp[j - 1][i];
        }
}

int get_lca(int v, int u)
{
    int l = tin[v], r = tin[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1, lca = dp[len][r - (1 << len) + 1];
    if (depth[dp[len][l]] < depth[lca])
        lca = dp[len][l];
    return lca;
}

ll dist(int v, int u)
{
    int lca = get_lca(v, u);
    return depth[v] + depth[u] - 2 * depth[lca];
}

void init_tree()
{
    for (int i = 2; i <= n; i ++)
    {
        adj[p[i]].push_back({i, w[i]});
    }

    traverse(1);
}

bool cmp_tin(int a, int b)
{
    return tin[a] < tin[b];
}

vector < pair < int, ll > > vir_adj[maxn];

void clear_vir_tree(vector < int > st)
{
    for (int v : st)
        vir_adj[v].clear();
}

ll virtual_tree(vector < int > ver_st)
{
    sort(ver_st.begin(), ver_st.end(), cmp_tin); /// sort by dfs in time
    int sz = ver_st.size();
    for (int i = 1; i < sz; i ++)
    {
        st.push_back(get_lca(ver_st[i], ver_st[i - 1])); /// mark the additional vertices
    }

    sort(ver_st.begin(), ver_st.end(), cmp_tin); /// sort with additional

    vector < int > marked; /// contains marked vertices
    marked.push_back(ver_st[0]);
    for (int i = 1; i < st.size(); i ++)
        if (ver_st[i] != ver_st[i - 1]) /// remove duplicates
        marked.push_back(ver_st[i]);
    /// there is a function unique to do this
    /// but I hate it

    stack < int > st;
    int root = marked[0];
    st.push(root);
    for (int i = 1; i < marked.size(); i ++)
    {
        while(get_lca(st.top() && marked[i]) != st.top()) /// st can never be empty
            st.pop(); /// removing all vertexes from which we have gone up

        vir_adj[st.top()].push_back({marked[i], depth[marked[i]] - depth[st.top()]});
        /// adds edge from the parent of marked[i] to marked[i]
        /// edges on the path are compressed
    }

    /// solve query

    clear_vir_tree(marked);

}

void answer_queries()
{

}
void clear_data()
{
    for (int i = 1; i <= n; i ++)
    {
        adj[i].clear();
    }
    timer = 0;
}

void solve()
{
    input();
    init_tree();
    sparse_table();
    answer_queries();
    clear_data();
}

int main()
{
    int t;
    cin >> t;
    while(t --)
        solve();
    return 0;
}

Compilation message (stderr)

minerals.cpp: In function 'll virtual_tree(std::vector<int>)':
minerals.cpp:104:9: error: 'st' was not declared in this scope; did you mean 'sz'?
  104 |         st.push_back(get_lca(ver_st[i], ver_st[i - 1])); /// mark the additional vertices
      |         ^~
      |         sz
minerals.cpp:111:25: error: 'st' was not declared in this scope; did you mean 'sz'?
  111 |     for (int i = 1; i < st.size(); i ++)
      |                         ^~
      |                         sz
minerals.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 1; i < marked.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
minerals.cpp:122:44: error: too few arguments to function 'int get_lca(int, int)'
  122 |         while(get_lca(st.top() && marked[i]) != st.top()) /// st can never be empty
      |                                            ^
minerals.cpp:58:5: note: declared here
   58 | int get_lca(int v, int u)
      |     ^~~~~~~
minerals.cpp:134:1: warning: no return statement in function returning non-void [-Wreturn-type]
  134 | }
      | ^