oj.uz

Submission #780173

# Submission time Handle Problem Language Result Execution time Memory
780173 2023-07-12T07:07:27 Z Thanhs Factories (JOI14_factories) C++14
15 / 100
 8000 ms 475932 KB 
#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],f[MAXN];
ll n,timer,tin[MAXN],tout[MAXN],c,s,t,x[MAXN],y[MAXN],color[MAXN],vtn[MAXN],nn,vtcolor[MAXN],dep[MAXN],ans,dis[MAXN];
vector<pair<ll,ll>> g[MAXN],vtg[MAXN];
stack<pair<ll,ll>> stk;

void dfs(const ll& u,const ll& 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);
  ll t=2*n-1;
  FOR(i,1,63-__builtin_clzll(t)) FOR(j,0,t-(1ll<<i)) st[j][i]=min(st[j][i-1],st[j+(1ll<<i-1)][i-1]);
}

pair<ll,ll> lca(ll u,ll v)
{
  if(tin[u]>tin[v]) swap(u,v);
  ll 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 ll& u,const ll& 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 N,A[MAXN],B[MAXN],D[MAXN],S,X[MAXN],T,Y[MAXN];

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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24656 KB Output is correct
2 Correct 656 ms 37272 KB Output is correct
3 Correct 651 ms 36556 KB Output is correct
4 Correct 726 ms 37408 KB Output is correct
5 Correct 588 ms 37100 KB Output is correct
6 Correct 438 ms 36748 KB Output is correct
7 Correct 630 ms 36516 KB Output is correct
8 Correct 644 ms 37452 KB Output is correct
9 Correct 593 ms 37104 KB Output is correct
10 Correct 433 ms 36720 KB Output is correct
11 Correct 630 ms 36516 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24380 KB Output is correct
2 Execution timed out 8026 ms 475932 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24656 KB Output is correct
2 Correct 656 ms 37272 KB Output is correct
3 Correct 651 ms 36556 KB Output is correct
4 Correct 726 ms 37408 KB Output is correct
5 Correct 588 ms 37100 KB Output is correct
6 Correct 438 ms 36748 KB Output is correct
7 Correct 630 ms 36516 KB Output is correct
8 Correct 644 ms 37452 KB Output is correct
9 Correct 593 ms 37104 KB Output is correct
10 Correct 433 ms 36720 KB Output is correct
11 Correct 630 ms 36516 KB Output is correct
12 Correct 14 ms 24380 KB Output is correct
13 Execution timed out 8026 ms 475932 KB Time limit exceeded
14 Halted 0 ms 0 KB -