제출 #246712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246712		LifeHappen__	공장들 (JOI14_factories)	C++14	컴파일 에러	0 ms	0 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

#define forinc(a, b, c) for(int a = b, _c = c; a <= _c; ++a)
#define fordec(a, b, c) for(int a = b, _c = c; a >= _c; --a)
#define rep(i, a) forinc(i, 1, a)
#define repv(i, a) forinc(i, 0, a - 1)
#define forv(a, b) for(auto &a : b)

#define ii pair<int, int>
#define fi first
#define se second
#define reset(f, x) memset(f, x, sizeof(f))
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair

#define bit(x, i) (x >> (i - 1) & 1ll)
#define on(x, i) (x | (1ll << (i - 1)))
#define off(x, i) (x & ~(1ll << (i - 1)))

const int N = 5e5 + 5;
const int INF = 1e18;
int n, que, dep[N], pd[N][32], d[N], in[N], id, out[N], dd[N], s, t;
int pf[N], sf[N], ans;
int st[N], top;
vector <ii> ad[N];
vector <ii> adj[N];
vector <int> del;
void dfs(int u, int par) {
    in[u] = ++id;
    forinc(i, 1, log2(n)) pd[u][i] = pd[pd[u][i - 1]][i - 1];
    forv(v, ad[u]) if(v.fi != par) {
        pd[v.fi][0] = u;
        dep[v.fi] = dep[u] + 1;
        d[v.fi] = d[u] + v.se;
        dfs(v.fi, u);
    }
    out[u] = ++id;
}
int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    int dif = dep[u] - dep[v];
    fordec(i, log2(n), 0) if(dif >> i & 1) u = pd[u][i];
    if(u == v) return u;
    fordec(i, log2(n), 0) if(pd[u][i] != pd[v][i]) u = pd[u][i], v = pd[v][i];
    return pd[u][0];
}
bool cmp(int x, int y) {
    return in[x] < in[y];
}
int dist(int u, int v) {
    int par = lca(u, v);
    return d[u] + d[v] - 2 * d[par];
}
void dfs1(int u, int par) {
    long long &x = pf[u], &y = sf[u];
    x = dd[u]&1 ? 0 : INF, y = dd[u]&2 ? 0 : INF;
    forv(v, adj[u]) {
        if(v.fi != par) {
            dfs1(v.fi, u);
            x = min(x, pf[v.fi] + v.se);
            y = min(y, sf[v.fi] + v.se);
        }
    }
    ans = min(ans, x + y);
}
void Init(int n, int A[], int B[], int D[]) {
    forinc(i, 0, n - 2) {
        int u = A[i], v = B[i], c = D[i];
        u++; v++;
        ad[u].eb(v, c);
        ad[v].eb(u, c);
    }
    dfs(1, -1);
}
long long Query(int s, int X[], int t, int Y[]) {
    ans = INF;
    //s = _s, t  = _t;
    vector <int> node;
    forinc(i, 0, s - 1) {
        int v = X[i];
        v++, dd[v] = 1, node.pb(v);
    }
    forinc(i, 0, t - 1) {
        int v = Y[i];
        v++, dd[v] |= 2, node.pb(v);
    }
    sort(all(node), [](int x, int y){return ii(st[x],out[x])<ii(st[y],out[y]);});
    forinc(i, 0, node.size() - 2) node.pb(lca(node[i], node[i + 1]));
    sort(all(node)); node.erase(unique(all(node)), end(node));
    sort(all(node), cmp);
    top = 0;
    forinc(i, 0, node.size() - 1) {
        while(top && out[node[i]] >= out[node[st[top]]]) top--;
        if(top) {
            int u = node[i], v = node[st[top]];
            adj[u].eb(v, dist(u, v));
            adj[v].eb(u, dist(v, u));
        }
        st[++top] = i;
    }
    dfs1(node[0], -1);
    forv(w, node) pf[w] = sf[w] = dd[w] = 0, adj[w].clear();
    return ans;
}
/*
signed main() {
    ios_base::sync_with_stdio(false);
    if(fopen("inp.txt", "r")) {
        freopen("inp.txt", "r", stdin);
        //freopen("out.txt", "w", stdout);
    }
    int _n, que;
    static int a[5000], b[5000], c[5000];
    cin >> _n >> que;
    forinc(i, 0, _n - 2) {
        int u, v, c;
        cin >> a[i] >> b[i] >> d[i];
    }
    Init(_n, a, b, d);
    dfs(1, -1);
    while(que--) {
        int _s, _t, v;
        cin >> _s >> _t;
        static int p[5005], q[5005];
        forinc(i, 0, _s - 1) cin >> v, p[i] = v;
        forinc(i, 0, _t - 1) cin >> v, q[i] = v;
        cout << Query(_s, p, _t, q) << '\n';
    }
}
*/

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp:32:17: warning: overflow in implicit constant conversion [-Woverflow]
 const int INF = 1e18;
                 ^~~~
factories.cpp: In function 'void dfs1(int, int)':
factories.cpp:66:24: error: cannot bind non-const lvalue reference of type 'long long int&' to an rvalue of type 'long long int'
     long long &x = pf[u], &y = sf[u];
                    ~~~~^
factories.cpp:66:36: error: cannot bind non-const lvalue reference of type 'long long int&' to an rvalue of type 'long long int'
     long long &x = pf[u], &y = sf[u];
                                ~~~~^
factories.cpp:71:39: error: no matching function for call to 'min(long long int&, int)'
             x = min(x, pf[v.fi] + v.se);
                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
factories.cpp:71:39: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
             x = min(x, pf[v.fi] + v.se);
                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
factories.cpp:71:39: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
             x = min(x, pf[v.fi] + v.se);
                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
factories.cpp:71:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
             x = min(x, pf[v.fi] + v.se);
                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
factories.cpp:71:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
             x = min(x, pf[v.fi] + v.se);
                                       ^
factories.cpp:72:39: error: no matching function for call to 'min(long long int&, int)'
             y = min(y, sf[v.fi] + v.se);
                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
factories.cpp:72:39: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
             y = min(y, sf[v.fi] + v.se);
                                       ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
factories.cpp:72:39: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
             y = min(y, sf[v.fi] + v.se);
                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
factories.cpp:72:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
             y = min(y, sf[v.fi] + v.se);
                                       ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
factories.cpp:72:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
             y = min(y, sf[v.fi] + v.se);
                                       ^
factories.cpp:75:25: error: no matching function for call to 'min(int&, long long int)'
     ans = min(ans, x + y);
                         ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
factories.cpp:75:25: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
     ans = min(ans, x + y);
                         ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
factories.cpp:75:25: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
     ans = min(ans, x + y);
                         ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
factories.cpp:75:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
     ans = min(ans, x + y);
                         ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
factories.cpp:75:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
     ans = min(ans, x + y);
                         ^