Submission #780204

#	Time	Username	Problem	Language	Result	Execution time	Memory
780204		Thanhs	Factories (JOI14_factories)	C++14	100 / 100	7884 ms	518916 KiB

factories

#include "factories.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef stack<ll> sll;
typedef queue<ll> qll;
typedef deque<ll> dll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
 
// #define int long long
#define endl '\n'
#define pb push_back
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define BACK(i,a,b) for(int i = a; i >= b; i--)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define bp __builtin_popcountll
#define gcd __gcd
#define bit(i,n) ((n>>i)&1)
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
 
const int MAXN = (5e5)+5;
// const ll SQRT = 4;
const long long inf = 1e18;
const long long MOD = 1e9+7;

pair<ll,ll> st[2*MAXN][25],a[MAXN],nd[MAXN];
pair<ll,ll> f[MAXN];
int n,timer,tin[MAXN],tout[MAXN],c,s,t,x[MAXN],y[MAXN],color[MAXN],vtn[MAXN],nn,vtcolor[MAXN],dep[MAXN];
ll ans,dis[MAXN];
vector<pair<int,ll>> g[MAXN],vtg[MAXN];
stack<pair<int,int>> stk;

void dfs(const int& u,const int& p)
{
  st[timer][0]={dep[u],u};
  tin[u]=timer++;
  for(auto v:g[u]) if(v.fi!=p) 
  {
    dep[v.fi]=dep[u]+1; 
    dis[v.fi]=dis[u]+v.se; 
    dfs(v.fi,u);
    st[timer++][0]={dep[u],u};
  }
  tout[u]=timer;
}

void build()
{
  dfs(0,-1);
  int t=2*n-1;
  FOR(i,1,31-__builtin_clz(t)) FOR(j,0,t-(1<<i)) st[j][i]=min(st[j][i-1],st[j+(1ll<<i-1)][i-1]);
}

pair<int,int> lca(int u,int v)
{
  if(tin[u]>tin[v]) swap(u,v);
  int t=__lg(tin[v]-tin[u]+1);
  return min(st[tin[u]][t],st[tin[v]-(1<<t)+1][t]);
}

void buildvt()
{
  FOR(i,0,c-1) nd[i]=a[i];
  FOR(i,0,c-2) 
  {
    ll l=lca(a[i].se,a[i+1].se).se;
    nd[c+i]={tin[l],l};
  }
  sort(nd,nd+2*c-1);
  nn=0;
  vtg[nn].clear();
  vtcolor[nn]=color[nd[0].se];
  vtn[nn++]=nd[0].se;
  while(!stk.empty()) stk.pop();
  stk.push({nd[0].se,0});
  FOR(i,1,2*c-2)
  {
    if(nd[i].se==stk.top().fi) continue;
    while(!stk.empty()&&!(tin[nd[i].se]>tin[stk.top().fi]&&tout[nd[i].se]<=tout[stk.top().fi])) stk.pop();
    vtcolor[nn]=color[nd[i].se]; vtn[nn]=nd[i].se;
    vtg[nn].clear();
    vtg[nn].pb({stk.top().se,dis[nd[i].se]-dis[stk.top().fi]});
    vtg[stk.top().se].pb({nn,dis[nd[i].se]-dis[stk.top().fi]});
    stk.push({nd[i].se,nn++});
  }
}

pair<ll,ll> solve(const int& u,const int& p)
{
  if(f[u]!=make_pair(1ll*-1,1ll*-1)) return f[u];
  pair<ll,ll> res={inf,inf};
  if(vtcolor[u]==-1) res.se=0;
  else if(vtcolor[u]==1) res.fi=0;
  for(auto v:vtg[u]) if(v.fi!=p) {setmin(res.fi,solve(v.fi,u).fi+v.se); setmin(res.se,solve(v.fi,u).se+v.se);}
  return f[u]=res;
}

ll Query(int S,int X[],int T,int Y[])
{
  s=S; t=T; c=s+t;
  FOR(i,0,n-1) color[i]=vtcolor[i]=0;
  FOR(i,0,s-1) {x[i]=X[i]; color[x[i]]=-1; a[i]={tin[x[i]],x[i]};}
  FOR(i,0,t-1) {y[i]=Y[i]; color[y[i]]=1; a[s+i]={tin[y[i]],y[i]};}
  sort(a,a+c);
  buildvt();
  FOR(i,0,nn-1) f[i]={-1,-1};
  ans=LLONG_MAX;
  FOR(i,0,nn-1) setmin(ans,solve(i,-1).fi+solve(i,-1).se);
  return ans;
}

void Init(int N,int A[],int B[],int D[])
{
  n=N;
  FOR(i,0,n-1) g[i].clear();
  FOR(i,0,n-2)
  {
    g[A[i]].pb({B[i],D[i]});
    g[B[i]].pb({A[i],D[i]});
  }
  build();
}

Compilation message (stderr)

factories.cpp: In function 'void build()':
factories.cpp:61:86: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   61 |   FOR(i,1,31-__builtin_clz(t)) FOR(j,0,t-(1<<i)) st[j][i]=min(st[j][i-1],st[j+(1ll<<i-1)][i-1]);
      |                                                                                     ~^~

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