Submission #1281945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281945		escobrand	Factories (JOI14_factories)	C++20	100 / 100	4633 ms	341660 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<array<ll,2>> adj[maxn];
bool c[maxn];
vector<array<ll,2>> pre[maxn];
int s[maxn];
ll mn[maxn];

void dfs(int i,int p)
{
  s[i] = 1;
  for(array<ll,2> k : adj[i])
  {
    if(k[0]==p||c[k[0]])continue;
    dfs(k[0],i);
    s[i] += s[k[0]];
  }
}

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

void fill(int i,int p,int cen,ll dis)
{
  for(array<ll,2> k : adj[i])
  {
    if(c[k[0]]||k[0]==p)continue;
    fill(k[0],i,cen,dis+k[1] );
  }
  pre[i].pb({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(array<ll,2> k : adj[cen])
  {
    if(!c[k[0]])decompose(k[0]);
  }
}

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({B[i],D[i]});
    adj[B[i]].pb({A[i],D[i]});
  }
  for(int i = 1;i<=N;i++)mn[i] = inf;
  
  decompose(1);
}

void up(int i)
{
  for(array<ll,2> k : pre[i]) mn[k[0]] = min(mn[k[0]],k[1] );
}
ll ans;

void cal(int i)
{
  for(array<ll,2> k : pre[i]) ans = min(ans,mn[k[0]] + k[1] );
}

void fix(int i)
{
  for(array<ll,2> k : pre[i]) 
  {
    if(mn[k[0]]!=inf)mn[k[0]] = inf;
    // else break;
  }
}
long long Query(int S, int X[], int T, int Y[]) {
  ans = inf;
  for(int i = 0;i<S;i++)
  {
    X[i]++;
    up(X[i]);
  }
  
  for(int i  = 0;i<T;i++)
  {
    Y[i]++;
    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