Submission #780473

#	Time	Username	Problem	Language	Result	Execution time	Memory
780473		trucmai	Factories (JOI14_factories)	C++17	100 / 100	2360 ms	482472 KiB

factories

//i_love_aisukiuwu
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
	#include "/home/trucmai/.vim/tools.h"
	#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
	#else
	#define debug(x...)
#endif

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

const int MN1 = 1e6 + 5,MN2 = 1e4 + 5,LOG = 20;
const ll MOD = 1e9 + 7,INF = 1e18;
ll tin[MN1],tout[MN1],dis[MN1],el[MN1],h[MN1],cc[MN1]; 
ll sptin[MN1],sptout[MN1];
pi sp[MN1][LOG]; 
vector<pi>adj[MN1],vt[MN1];
ll timer = 0,sptimer = 0;

void dfs(ll u,ll pre){ 
  tin[u] = ++timer;
  sp[++sptimer][0] = {h[u],u};
  sptin[u] = sptimer;
  for(auto [v,w] : adj[u]){
    if(v == pre) continue;
    dis[v] = dis[u] + w;
    h[v] = h[u] + 1;
    dfs(v,u);
    sp[++sptimer][0] = {h[u],u};
  }
  tout[u] = timer;
}

ll lg_floor(ll u){return 63 - __builtin_clzll(u);}

void sparse(){
  for(ll i = 1;i < LOG;++i)
    for(ll j = 0;j + (1LL<<i) - 1 <= sptimer;++j)
      sp[j][i] = min(sp[j][i-1],sp[j + (1LL<<(i-1))][i-1]);
}

ll lca(ll u,ll v){
  ll tu = sptin[u],tv = sptin[v];
  if(tu > tv) swap(tu,tv);
  ll k = lg_floor(tv - tu + 1); 
  return min(sp[tu][k],sp[tv - (1LL<<k) + 1][k]).se;
}

pi dpfs(ll u,ll pre,ll &res){
  pi short_dis = {INF,INF}; 
  //cout << u << " " << pre << " " << res << endl; 
  if(cc[u] == 0) short_dis.fi = 0;
  else if(cc[u] == 1) short_dis.se = 0;
  for(auto [v,w] : vt[u]){
    if(v == pre) continue; 
    pi tmp = dpfs(v,u,res);
    //cout << tmp.fi << " " << tmp.se << endl;
    res = min(res, min(short_dis.fi + tmp.se, short_dis.se + tmp.fi) + w);
    short_dis.fi = min(short_dis.fi,tmp.fi + w);
    short_dis.se = min(short_dis.se,tmp.se + w);
  }
  debug(u,pre,short_dis,res);
  return short_dis;
}

void Init(int n, int a[],int b[],int d[]){
  mset(cc,-1);
  for(ll i = 0;i < n;++i){
    adj[a[i]].emplace_back(b[i],d[i]);
    adj[b[i]].emplace_back(a[i],d[i]);
  }
  dfs(0,0); sparse(); 
}

long long Query(int s,int x[],int t,int y[]){ 
  vector<ll>a;
  for(ll i = 0;i < s;++i){
    a.emplace_back(x[i]);
    cc[x[i]] = 0;
  }
  for(ll i = 0;i < t;++i){
    a.emplace_back(y[i]);
    cc[y[i]] = 1;
  }
  sort(all(a),[&](ll x,ll y){return tin[x] < tin[y];});
  for(ll i = 0;i + 1 < s + t;++i) a.push_back(lca(a[i],a[i+1]));  
  sort(all(a),[&](ll x,ll y){return tin[x] < tin[y];});
  a.resize(unique(all(a))-a.begin()); 
  auto is_anc=[&](ll u,ll v)->bool{
    return tin[u] <= tin[v] && tout[u] >= tin[v];
  }; 
  //create virtual tree
  stack<ll>st;
  auto add=[&](ll u,ll v,ll w)->void{
    vt[u].emplace_back(v,w); 
    vt[v].emplace_back(u,w);
  };
  for(ll i = 0;i < a.size();++i){
    while(!st.empty() && !is_anc(st.top(),a[i])) st.pop(); 
    if(!st.empty()) add(st.top(),a[i],dis[a[i]] - dis[st.top()]);
    st.push(a[i]); 
  } 
  ll res = INF;
  dpfs(a[0],0,res);
  for(ll i = 0;i < a.size();++i) vt[a[i]].clear();
  for(ll i = 0;i < s;++i) cc[x[i]] = -1;
  for(ll i = 0;i < t;++i) cc[y[i]] = -1;
  return res;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:111:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for(ll i = 0;i < a.size();++i){
      |                ~~^~~~~~~~~~
factories.cpp:118:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for(ll i = 0;i < a.size();++i) vt[a[i]].clear();
      |                ~~^~~~~~~~~~

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