oj.uz

답안 #780157

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780157 2023-07-12T07:02:39 Z Thanhs 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 475772 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 = 1e15;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 24552 KB Output is correct
2 Correct 671 ms 37348 KB Output is correct
3 Correct 662 ms 36624 KB Output is correct
4 Correct 663 ms 37428 KB Output is correct
5 Correct 598 ms 37068 KB Output is correct
6 Correct 465 ms 36804 KB Output is correct
7 Correct 617 ms 36516 KB Output is correct
8 Correct 604 ms 37412 KB Output is correct
9 Correct 570 ms 37232 KB Output is correct
10 Correct 451 ms 36876 KB Output is correct
11 Correct 615 ms 36456 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24404 KB Output is correct
2 Execution timed out 8109 ms 475772 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 24552 KB Output is correct
2 Correct 671 ms 37348 KB Output is correct
3 Correct 662 ms 36624 KB Output is correct
4 Correct 663 ms 37428 KB Output is correct
5 Correct 598 ms 37068 KB Output is correct
6 Correct 465 ms 36804 KB Output is correct
7 Correct 617 ms 36516 KB Output is correct
8 Correct 604 ms 37412 KB Output is correct
9 Correct 570 ms 37232 KB Output is correct
10 Correct 451 ms 36876 KB Output is correct
11 Correct 615 ms 36456 KB Output is correct
12 Correct 15 ms 24404 KB Output is correct
13 Execution timed out 8109 ms 475772 KB Time limit exceeded
14 Halted 0 ms 0 KB -