제출 #1281852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281852		escobrand	공장들 (JOI14_factories)	C++20	0 / 100	19 ms	972 KiB

factories

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

using namespace std;
#define fi first
#define se second
#define ll long long
#define all(v) v.begin(),v.end()
#define mk make_pair
#define pb push_back
#define eb emplace_back
typedef pair<ll,ll> pii;

const int maxn = 5e5 + 10;
vector<pii> adj[maxn];
int in[maxn],out[maxn],t,p[maxn][20];
ll d[maxn];

void dfs(int i,int pa)
{
  in[i] = ++t;
  p[i][0] = pa;
  for(int j = 1;j<20;j++)p[i][j] = p[p[i][j-1]][j-1];
  for(pii k :adj[i])
  {
    if(k.fi==pa)continue;
    d[k.fi] = d[i] + k.se;
    dfs(k.fi,i);
  }
  out[i] = t;
}

int lca(int u,int v)
{
  if(in[u] > in[v])swap(u,v);
  if(u==v)return u;
  for(int j = 19;j>=0;j--)
  {
    if(p[v][j] && in[p[v][j]] > in[u])v = p[v][j];
  }
  return p[v][0];
}

bool cmp(int &i,int &j)
{
  return in[i]<in[j];
}

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

bool c[maxn];

void filter(vector<int> & v)
{
  sort(all(v),cmp);
  v.resize(unique(all(v))-v.begin());
}

vector<pii> com_adj[maxn];

priority_queue<pii,vector<pii>,greater<pii>>q;
ll dp[maxn];

long long Query(int S, int X[], int T, int Y[]) {
  
  vector<int> v;
  
  for(int i = 0;i<S;i++) 
  {
    X[i]++;
    v.pb(X[i]);
    q.push(mk(0,X[i]));
  }
  
  for(int i = 0;i<T;i++) 
  {
    Y[i]++;
    c[Y[i]]=1;
    v.pb(Y[i]);
  }
  filter(v);
  int n = v.size();
  for(int i = 1;i<n;i++)
  {
    v.pb(lca(v[i],v[i-1]));
  }
  filter(v);
  
  stack<int> st;
  for(int k : v)
  {
    while(st.size()&&out[st.top()]<out[k])st.pop();
    com_adj[k].clear();
    if(st.size())
    {
      int p = st.top();
      com_adj[k].pb(mk(p,d[k] - d[p]));
      com_adj[p].pb(mk(k,d[k] - d[p]));
      // cout<<p<<' '<<k<<' '<<d[k]-d[p]<<'\n';
    }
    st.push(k);
    dp[k] = LLONG_MAX;
    // cout<<k<<' '<<in[k]<<' '<<out[k]<<'\n';;
  }
  for(int i = 0;i<S;i++) 
  {
    dp[X[i]] = 0;
  }
  ll ans = LLONG_MAX;
  while(q.size())
  {
    ll w = q.top().fi;
    int i = q.top().se;
    q.pop();
    if(w != dp[i])continue;
    if(c[i])
    {
      ans = w;
      break;
    }
    for(pii k : com_adj[i])
    {
      if(dp[k.fi] > w + k.se)
      {
        q.push(mk(dp[k.fi] = w + k.se,k.fi));
      }
    }
  }
  
  
  for(int k : v)
  {
    c[k]=0;
  }
  
  return ans;
}

// int main()
// {
//     ios_base::sync_with_stdio(false);
//     cin.tie(0);
    
//     int n,t;
//     cin>>n>>t;
//     int u[n-1],v[n-1],w[n-1];
//     for(int i = 0;i<n-1;i++)
//     {
//       cin>>u[i]>>v[i]>>w[i];
//     }
    
//     Init(n,u,v,w);
    
//     while(t--)
//     {
//       int n,m;
//       cin>>n>>m;
//       int u[n],v[m];
//       for(int i = 0;i<n;i++)
//         cin>>u[i];
//       for(int i = 0;i<m;i++)
//         cin>>v[i];
//       cout<<Query(n,u,m,v)<<'\n';
//     }
    
    
//     return 0;
// }

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67