제출 #1281927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281927		escobrand	공장들 (JOI14_factories)	C++20	100 / 100	4369 ms	341664 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;
const ll inf = 1e17;
vector<pii> adj[maxn];
bool c[maxn];
vector<pii> pre[maxn];
int s[maxn];
ll mn[maxn];

void dfs(int i,int p)
{
  s[i] = 1;
  for(pii k : adj[i])
  {
    if(k.fi==p||c[k.fi])continue;
    dfs(k.fi,i);
    s[i] += s[k.fi];
  }
}

int fi(int i,int p,int sz)
{
  for(pii k : adj[i])
  {
    if(k.fi==p||c[k.fi])continue;
    if(s[k.fi] * 2 > sz)return fi(k.fi,i,sz);
  }
  
  return i;
}

void fill(int i,int p,int cen,ll dis)
{
  for(pii k : adj[i])
  {
    if(c[k.fi]||k.fi==p)continue;
    fill(k.fi,i,cen,dis+k.se);
  }
  pre[i].pb(mk(cen,dis));
}

void decompose(int i)
{
  dfs(i,0);
  int cen = fi(i,0,s[i]);
  fill(cen,0,cen,0);
  c[cen] = 1;
  // cout<<cen<<'\n';
  for(pii k : adj[cen])
  {
    if(!c[k.fi])decompose(k.fi);
  }
}

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]));
  }
  for(int i = 1;i<=N;i++)mn[i] = inf;
  
  decompose(1);
}

void up(int i)
{
  for(pii k : pre[i]) mn[k.fi] = min(mn[k.fi],k.se);
}

ll cal(int i)
{
  ll ans = inf;
  for(pii k : pre[i]) ans = min(ans,mn[k.fi] + k.se);
  return ans;
}

void fix(int i)
{
  for(pii k : pre[i]) 
  {
    if(mn[k.fi]!=inf)mn[k.fi] = inf;
    // else break;
  }
}

long long Query(int S, int X[], int T, int Y[]) {
  ll ans = inf;
  for(int i = 0;i<S;i++)
  {
    X[i]++;
    up(X[i]);
  }
  
  for(int i  = 0;i<T;i++)
  {
    Y[i]++;
    ans=min(ans,cal(Y[i]));
  }
  
  for(int i = 0;i<S;i++)fix(X[i]);
  
  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: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67