oj.uz

Submission #780153

# Submission time Handle Problem Language Result Execution time Memory
780153 2023-07-12T07:01:25 Z Thanhs Factories (JOI14_factories) C++14
15 / 100
 8000 ms 475996 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 26 ms 24660 KB Output is correct
2 Correct 647 ms 37240 KB Output is correct
3 Correct 620 ms 36576 KB Output is correct
4 Correct 626 ms 37552 KB Output is correct
5 Correct 559 ms 37096 KB Output is correct
6 Correct 415 ms 36848 KB Output is correct
7 Correct 615 ms 36572 KB Output is correct
8 Correct 607 ms 37456 KB Output is correct
9 Correct 569 ms 37100 KB Output is correct
10 Correct 406 ms 36876 KB Output is correct
11 Correct 604 ms 36512 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24660 KB Output is correct
2 Correct 647 ms 37240 KB Output is correct
3 Correct 620 ms 36576 KB Output is correct
4 Correct 626 ms 37552 KB Output is correct
5 Correct 559 ms 37096 KB Output is correct
6 Correct 415 ms 36848 KB Output is correct
7 Correct 615 ms 36572 KB Output is correct
8 Correct 607 ms 37456 KB Output is correct
9 Correct 569 ms 37100 KB Output is correct
10 Correct 406 ms 36876 KB Output is correct
11 Correct 604 ms 36512 KB Output is correct
12 Correct 14 ms 24404 KB Output is correct
13 Execution timed out 8103 ms 475996 KB Time limit exceeded
14 Halted 0 ms 0 KB -