Submission #852438

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
852438	2023-09-21T19:39:53 Z	epicci23	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KB

factories

#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define sz(x) ((int)(x).size())
const int N = 5e5 + 5;
const int LOG = 30;
const long long INF = 1e18;
vector<array<long long,2>> v[N];  
int tin[N],tout[N];
long long depth[N];
int t=0;
int lift[N][LOG];

void dfs(int c,int p,long long d){
  depth[c]=d;
  tin[c]=t++;
  tout[c]=tin[c];
  lift[c][0]=p;
  for(int i=1;i<LOG;i++) lift[c][i]=lift[lift[c][i-1]][i-1];
  for(auto x:v[c]){
    if(x[0]==p) continue;
    dfs(x[0],c,d+x[1]);
    tout[c]=max(tout[c],tout[x[0]]);
  }
}

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

bool check(int a,int b){
  return tin[a] <= tin[b] && tin[b]<=tout[a];
}

int lca(int a,int b){
  if(check(a,b)) return a;
  for(int i=LOG-1;i>=0;i--){
    if(!check(lift[a][i],b)) a=lift[a][i];
  }
  return lift[a][0];
}


long long Query(int S, int X[], int T, int Y[]){
  
  long long ans=INF;
  vector<pair<int,int>> cur;
  for(int i=0;i<S;i++) cur.pb({X[i],0});
  for(int i=0;i<T;i++) cur.pb({Y[i],1});

  map<int,int> vis;
  for(int i=0;i<sz(cur);i++) vis[cur[i].first]=1;

  sort(cur.begin(),cur.end(),[&](pair<int,int> i,pair<int,int> j){
    return tin[i.first] < tin[j.first];
  });

  vector<pair<int,int>> todo;

  for(int i=1;i<sz(cur);i++){
    if(!vis[lca(cur[i-1].first,cur[i].first)]){
     todo.pb({lca(cur[i-1].first,cur[i].first),2});
     vis[lca(cur[i-1].first,cur[i].first)]=1;
    }
  }

  for(auto x:todo) cur.pb(x);

  sort(cur.begin(),cur.end(),[&](pair<int,int> i,pair<int,int> j){
    return tin[i.first] < tin[j.first];
  });

  cur.erase(unique(cur.begin(), cur.end()),cur.end());

  vector<pair<int,long long>> g2[sz(cur) + 5];
  array<long long,2> dp[sz(cur)+5];
  
  fill(dp,dp+sz(cur)+5,make_pair(-1,-1));

  stack<int> s;
  s.push(0);

  for(int i=1;i<(int)cur.size();i++){
    int c = cur[i].first;
    while(!check(cur[s.top()].first,c)) s.pop();
    g2[s.top()].pb({i,depth[c]-depth[cur[s.top()].first]});
    s.push(i);
  }

  for(int i=sz(cur)-1;i>=0;i--){
    if(cur[i].second==0) dp[i][0]=depth[cur[i].first];
    else if(cur[i].second==1) dp[i][1]=depth[cur[i].first];

    for(auto x:g2[i]){
      if(dp[x.first][0]!=-1) dp[i][0]=min(dp[i][0],dp[x.first][0]+x.second);
      if(dp[x.first][1]!=-1) dp[i][1]=min(dp[i][1],dp[x.first][1]+x.second);
    }
    if(dp[i][0]!=-1 && dp[i][1]!=-1) ans=min(ans,dp[i][0]+dp[i][1]);
  }

  return ans;
}

Compilation message

In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from factories.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h: In instantiation of 'typename __gnu_cxx::__enable_if<(! std::__is_scalar<_Tp>::__value), void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = std::array<long long int, 2>*; _Tp = std::pair<int, int>; typename __gnu_cxx::__enable_if<(! std::__is_scalar<_Tp>::__value), void>::__type = void]':
/usr/include/c++/10/bits/stl_algobase.h:914:21:   required from 'void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = std::array<long long int, 2>*; _Tp = std::pair<int, int>]'
/usr/include/c++/10/bits/stl_algobase.h:944:20:   required from 'void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = std::array<long long int, 2>*; _Tp = std::pair<int, int>]'
factories.cpp:83:40:   required from here
/usr/include/c++/10/bits/stl_algobase.h:861:11: error: no match for 'operator=' (operand types are 'std::array<long long int, 2>' and 'const std::pair<int, int>')
  861 |  *__first = __value;
      |  ~~~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/10/tuple:39,
                 from /usr/include/c++/10/functional:54,
                 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/array:94:12: note: candidate: 'constexpr std::array<long long int, 2>& std::array<long long int, 2>::operator=(const std::array<long long int, 2>&)'
   94 |     struct array
      |            ^~~~~
/usr/include/c++/10/array:94:12: note:   no known conversion for argument 1 from 'const std::pair<int, int>' to 'const std::array<long long int, 2>&'
/usr/include/c++/10/array:94:12: note: candidate: 'constexpr std::array<long long int, 2>& std::array<long long int, 2>::operator=(std::array<long long int, 2>&&)'
/usr/include/c++/10/array:94:12: note:   no known conversion for argument 1 from 'const std::pair<int, int>' to 'std::array<long long int, 2>&&'