Submission #780065

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
780065	2023-07-12T06:24:28 Z	cheat_when_I_was_young	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KB

factories

#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const int NM = 5e5 + 5;

int in[NM], d[NM], h[NM];
vector<int> tour;
vector<pair<int,int>> adj[NM];

void dfs(int u, int par) {
    in[u] = tour.size();
    tour.push_back(u);
    for (auto &vv: adj[u]) {
        int v = vv.first, w = vv.second;
        if (v == par) continue;
        d[v] = d[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
        tour.push_back(u);
    }
}

const int LG = __lg(NM) + 1;

pair<int,int> ST[LG][NM];

void build() {
    for (int i = 0; i < (int)tour.size(); ++i)
        ST[0][i] = {h[tour[i]], tour[i]};
    for (int j = 1; j < LG; ++j)
        for (int i = 0; i + (1<<j) - 1 < (int)tour.size(); ++i)
            ST[j][i] = min(ST[j-1][i], ST[j-1][i + (1<<(j-1))]);
}

int lca(int u, int v) {
    int l = in[u], r = in[v];
    if (l > r) swap(l, r);
    int k = __lg(r - l + 1);
    return min(ST[k][l], ST[k][r - (1<<k) + 1]).second;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; ++i) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    dfs(1, 1);
    build();
}

int color[NM];
vector<int> newAdj[NM], node;


bool cmp(int x, int y) {
    return in[x] < in[y];
}

long long Query(int S, int X[], int T, int Y[]) {

    for (int i = 0; i < S; ++i) color[X[i]] = 1;
    for (int i = 0; i < T; ++i) {
        if (color[Y[i]] == 1) {
            for (int j = 0; j < S; ++j) color[X[j]] = 1;
            for (int j = 0; j < T; ++j) color[Y[j]] = 1;
            return 0;
        }
        color[Y[i]] = 2;
    }

    for (int i = 0; i < S; ++i) node.push_back(X[i]);
    for (int i = 0; i < T; ++i) node.push_back(Y[i]);
    sort(node.begin(), node.end());
    int N = node.size();
    for (int i = 1; i < N; ++i) node.push_back({lca(node[i], node[i-1]), 0});
    sort(node.begin(), node.end());

    stack<int> s;
    for (int &i: node) {
        if (s.empty()) {
            s.push(i);
            continue;
        }
        while (!s.empty() && lca(i, s.top()) != s.top()) s.pop();
        if (!s.empty()) {
            newAdj[s.top()].push_back(i);
            newAdj[i].push_back(s.top());
            s.push(i);
        }
    }

    for (int &i: node) {
        color[i] = 0;
        newAdj[i].clear();
    }
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:76:76: error: no matching function for call to 'std::vector<int>::push_back(<brace-enclosed initializer list>)'
   76 |     for (int i = 1; i < N; ++i) node.push_back({lca(node[i], node[i-1]), 0});
      |                                                                            ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:1187: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]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const int&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203: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]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<int>::value_type&&' {aka 'int&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
factories.cpp:79:16: warning: control reaches end of non-void function [-Wreturn-type]
   79 |     stack<int> s;
      |                ^