oj.uz

Submission #780204

# Submission time Handle Problem Language Result Execution time Memory
780204 2023-07-12T07:14:53 Z Thanhs Factories (JOI14_factories) C++14
100 / 100
 7884 ms 518916 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];
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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24660 KB Output is correct
2 Correct 647 ms 37156 KB Output is correct
3 Correct 680 ms 36448 KB Output is correct
4 Correct 686 ms 37296 KB Output is correct
5 Correct 597 ms 37020 KB Output is correct
6 Correct 426 ms 36632 KB Output is correct
7 Correct 657 ms 36384 KB Output is correct
8 Correct 654 ms 37316 KB Output is correct
9 Correct 640 ms 37028 KB Output is correct
10 Correct 406 ms 36596 KB Output is correct
11 Correct 617 ms 36428 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24404 KB Output is correct
2 Correct 7249 ms 467288 KB Output is correct
3 Correct 4381 ms 473000 KB Output is correct
4 Correct 6853 ms 465032 KB Output is correct
5 Correct 7847 ms 515168 KB Output is correct
6 Correct 7884 ms 474112 KB Output is correct
7 Correct 1407 ms 121676 KB Output is correct
8 Correct 1741 ms 121076 KB Output is correct
9 Correct 1830 ms 127584 KB Output is correct
10 Correct 1947 ms 122932 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24660 KB Output is correct
2 Correct 647 ms 37156 KB Output is correct
3 Correct 680 ms 36448 KB Output is correct
4 Correct 686 ms 37296 KB Output is correct
5 Correct 597 ms 37020 KB Output is correct
6 Correct 426 ms 36632 KB Output is correct
7 Correct 657 ms 36384 KB Output is correct
8 Correct 654 ms 37316 KB Output is correct
9 Correct 640 ms 37028 KB Output is correct
10 Correct 406 ms 36596 KB Output is correct
11 Correct 617 ms 36428 KB Output is correct
12 Correct 16 ms 24404 KB Output is correct
13 Correct 7249 ms 467288 KB Output is correct
14 Correct 4381 ms 473000 KB Output is correct
15 Correct 6853 ms 465032 KB Output is correct
16 Correct 7847 ms 515168 KB Output is correct
17 Correct 7884 ms 474112 KB Output is correct
18 Correct 1407 ms 121676 KB Output is correct
19 Correct 1741 ms 121076 KB Output is correct
20 Correct 1830 ms 127584 KB Output is correct
21 Correct 1947 ms 122932 KB Output is correct
22 Correct 2764 ms 490728 KB Output is correct
23 Correct 7740 ms 492228 KB Output is correct
24 Correct 1898 ms 491684 KB Output is correct
25 Correct 7797 ms 495676 KB Output is correct
26 Correct 1735 ms 475328 KB Output is correct
27 Correct 7734 ms 518916 KB Output is correct
28 Correct 7073 ms 483584 KB Output is correct
29 Correct 1905 ms 474308 KB Output is correct
30 Correct 1995 ms 473488 KB Output is correct
31 Correct 2066 ms 474316 KB Output is correct
32 Correct 2225 ms 139148 KB Output is correct
33 Correct 2050 ms 135048 KB Output is correct
34 Correct 888 ms 120332 KB Output is correct
35 Correct 913 ms 119988 KB Output is correct
36 Correct 868 ms 120788 KB Output is correct
37 Correct 870 ms 120588 KB Output is correct