Submission #1082911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1082911	2024-09-02T05:31:18 Z	pemguimn	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KB

factories

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

const int maxN = 5e5 + 5, LOG = 20;
const long long INF = (long long) 1e18 + 5;
vector<pair<int, int>> adj[maxN];

int h[maxN], par[LOG][maxN];
long long w[maxN];
void dfs(int i, int pre){
    for(pair<int, int> e : adj[i]){
        int x = e.first, c = e.second;
        if(x == pre) continue;
        h[x] = h[i] + 1, w[x] = w[i] + c;
        par[0][x] = i;
        for(int j = 1; j < LOG; j++) par[j][x] = par[j - 1][par[j - 1][x]];
        dfs(x, i);
    }
}

int lca(int x, int y){
    if(h[x] < h[y]) swap(x, y);
    int d = h[x] - h[y];
    for(int i = 0; i < LOG; i++){
        if(d & (1 << i)) x = par[i][x];
    }
    if(x == y) return x;
    for(int i = LOG - 1; i >= 0; i--){
        if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
    }
    return par[0][x];
}
map<pair<int, int>, int> mp;

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(0, 0);
}

long long Query(int S, int X[], int T, int Y[]){
    long long ans = INF;
    for(int i = 0; i < S; i++){
        for(int j = 0; j < T; j++){
            if(mp.count({X[i], Y[j]})){
                ans = min(ans, mp[{X[i], Y[j]}]);
            } else{
                mp[{X[i], Y[j]}] = w[X[i]] + w[Y[j]] - 2 * w[lca(X[i], Y[j])];
                ans = min(ans, mp[{X[i], Y[j]}]);
            }
        }
    }
    return ans;
}

////void local(){
////    int n, q;
////    cin >> n >> q;
////    for(int i = 0; i < n - 1; i++){
////        int x, y, z; cin >> x >> y >> z;
////        adj[x].push_back({y, z}), adj[y].push_back({x, z});
////    }
////    dfs(0, 0);
////    for(int i = 1; i <= q; i++){
////        vector<int> X, Y;
////        int s, t;
////        cin >> s >> t;
////        while(s--) {int x; cin >> x; X.push_back(x);}
////        while(t--) {int x; cin >> x; Y.push_back(x);}
////
////        long long ans = INF;
////
////        for(int x : X){
////            for(int y : Y){
////                ans = min(ans, w[x] + w[y] - 2LL * w[lca(x, y)]);
////            }
////        }
////        cout << ans << '\n';
////    }
////}
//int main(){
//    ios_base::sync_with_stdio(0); cin.tie(0);
//
//    local();
//    return 0;
//}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:49:48: error: no matching function for call to 'min(long long int&, std::map<std::pair<int, int>, int>::mapped_type&)'
   49 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
factories.cpp:49:48: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<std::pair<int, int>, int>::mapped_type' {aka 'int'})
   49 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
factories.cpp:49:48: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<std::pair<int, int>, int>::mapped_type' {aka 'int'})
   49 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
factories.cpp:49:48: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   49 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
factories.cpp:49:48: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   49 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^
factories.cpp:52:48: error: no matching function for call to 'min(long long int&, std::map<std::pair<int, int>, int>::mapped_type&)'
   52 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
factories.cpp:52:48: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<std::pair<int, int>, int>::mapped_type' {aka 'int'})
   52 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
factories.cpp:52:48: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<std::pair<int, int>, int>::mapped_type' {aka 'int'})
   52 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
factories.cpp:52:48: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   52 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
factories.cpp:52:48: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   52 |                 ans = min(ans, mp[{X[i], Y[j]}]);
      |                                                ^