oj.uz

Submission #673968

# Submission time Handle Problem Language Result Execution time Memory
673968 2022-12-22T13:24:25 Z Cookie Factories (JOI14_factories) C++14
Compilation error
 0 ms 0 KB 
#include<bits/stdc++.h>

#include<fstream>
#include "factories.h"

using namespace std;
ifstream fin("INTERNET.INP");
ofstream fout("INTERNET.OUT");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>

const int mxn = 1e5, sq = 300, mxv = 1e4;


int n;
vt<pll>adj[mxn + 1];
ll sz[mxn + 1], par[mxn + 1], ans[mxn + 1];
vt<int>s, t;
map<int, ll>dis[mxn + 1];
bool vis[mxn + 1];
int dfs(int s, int pre){
    sz[s] = 1;
    for(auto [i, w]: adj[s]){
        if(i != pre && !vis[i]){
            dfs(i, s); sz[s] += sz[i];
        }
    }
    return(sz[s]);
}
int centroid(int s, int pre, int need){
    for(auto [i, w]: adj[s]){
        if(i != pre && !vis[i]){
            if(sz[i] * 2 > need)return(centroid(i, s, need));
        }
    }
    return(s);
}
void dfs2(int s, int c, int pre, ll d){
    dis[c][s] = d;
    for(auto [i, w]: adj[s]){
        if(i != pre && !vis[i]){
            dfs2(i, c, s, d + w);
        }
    }
}
void build(int s, int pre){
    int c = centroid(s, -1, dfs(s, -1));
    vis[c] = true; par[c] = pre;
    dis[c][c] = 0;
    for(auto [i, w]: adj[c]){
        if(i != pre && !vis[i]){
            dfs2(i, c,  c, w);
        }
    }
    for(auto [i, w]: adj[c]){
        if(!vis[i]){
            build(i, c);
        }
    }
}
void Init(int N, int A[], int B[], int D[]) {

    n = N;
    for(int i = 0; i < n - 1; i++){
        adj[A[i]].pb({B[i], D[i]}); adj[B[i]].pb({A[i], D[i]});
    }
    build(0, -1); //centroid decompsoing the tree
    for(int i = 1; i <= n; i++)ans[i] = 1e18;
}
void add(int x){
    for(int i = x; i != -1; i = par[i])ans[i] = min(ans[i], dis[i][x]);
}
void rem(int x){
    for(int i = x; i != -1; i = par[i])ans[i] = 1e18;
}
int see(int x){
    ll res = 1e18;
    for(int i = x; i != -1; i = par[i])res = min(res, ans[i] + dis[i][x]);
    return(res);
}
ll solve(){
    for(int i = 0; i < s.size(); i++)add(s[i]);
    ll res = 1e18;
    for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
    
    for(int i = 0; i < s.size(); i++)rem(s[i]);
    return(res);
}
long long Query(int S, int X[], int T, int Y[]) {
    s.clear(); t.clear();
    for(int i = 0; i < S; i++)s.pb(X[i]);
    for(int i = 0; i < T; i++)t.pb(Y[i]);
    
    return(solve());
 
}

Compilation message

factories.cpp: In function 'int dfs(int, int)':
factories.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [i, w]: adj[s]){
      |              ^
factories.cpp: In function 'int centroid(int, int, int)':
factories.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for(auto [i, w]: adj[s]){
      |              ^
factories.cpp: In function 'void dfs2(int, int, int, long long int)':
factories.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto [i, w]: adj[s]){
      |              ^
factories.cpp: In function 'void build(int, int)':
factories.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [i, w]: adj[c]){
      |              ^
factories.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for(auto [i, w]: adj[c]){
      |              ^
factories.cpp: In function 'long long int solve()':
factories.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < s.size(); i++)add(s[i]);
      |                    ~~^~~~~~~~~~
factories.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
      |                    ~~^~~~~~~~~~
factories.cpp:91:62: error: no matching function for call to 'min(int, long long int&)'
   91 |     for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
      |                                                              ^
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:91:62: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   91 |     for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
      |                                                              ^
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:91:62: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   91 |     for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
      |                                                              ^
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:91:62: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   91 |     for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
      |                                                              ^
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:91:62: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   91 |     for(int i = 0; i < t.size(); i++)res = min(see(t[i]), res);
      |                                                              ^
factories.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i = 0; i < s.size(); i++)rem(s[i]);
      |                    ~~^~~~~~~~~~