제출 #990742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990742		boyliguanhan	공장들 (JOI14_factories)	C++17	100 / 100	4322 ms	159068 KiB

factories

#include "factories.h"
#define M 1<<19
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll TRE[2][2*M],dep[M],dd[M];
ll q(ll*T,int i,int l,int r,int tl,int tr){
    if(l>tr||tl>r) return 1e18;
    if(tl<=l&&r<=tr) return T[i];
    return min(q(T,i*2,l,l+r>>1,tl,tr),
            q(T,i*2+1,l+r+2>>1,r,tl,tr));
}
void upd(ll*T,int i,int l,int r,int p,ll x){
    if(l==r)return void(T[i]=x);
    if(l+r>>1<p)
        upd(T,i*2+1,l+r+2>>1,r,p,x);
    else upd(T,i*2,l,l+r>>1,p,x);
    T[i]=min(T[i*2],T[i*2+1]);
}
int pos[M],in[M],out[M],bj[M][20],CC,n;
vector<pair<int,ll>>adj[M];
void dfs(int n){
    for(int i=1;i<20;i++)
        bj[n][i]=bj[bj[n][i-1]][i-1];
    in[n]=++CC,dd[n]=dd[bj[n][0]]+1;
    for(auto[i,w]:adj[n]) if(i-bj[n][0])
        dep[i]=dep[n]+w,bj[i][0]=n,dfs(i);
    out[n]=CC;
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i=1;i<2*M;i++)
        TRE[1][i]=TRE[0][i]=1e18;
    for(int i=0;i<N-1;i++)
        adj[A[i]].push_back({B[i],D[i]}),
        adj[B[i]].push_back({A[i],D[i]});
    n=N,dfs(0);
}
int lca(int a,int b){
    if(dd[a]>dd[b])swap(a,b);
    for(int i=20;i--;)
        if(dd[bj[b][i]]>=dd[a])
            b=bj[b][i];
    if(a==b)return a;
    for(int i=20;i--;)
        if(bj[b][i]-bj[a][i])
            a=bj[a][i],b=bj[b][i];
    return bj[a][0];
}
long long Query(int S, int X[], int T, int Y[]) {
    ll ans=1e18;
    vector<int>v;
    for(int i=0;i<S;i++) v.push_back(X[i]),
        upd(*TRE,1,1,n,in[X[i]],dep[X[i]]);
    for(int i=0;i<T;i++) v.push_back(Y[i]),
        upd(TRE[1],1,1,n,in[Y[i]],dep[Y[i]]);
    sort(v.begin(),v.end(),[](int a,int b){return in[a]<in[b];});
    for(int i=1;i<S+T;i++){
        int x=lca(v[i],v[i-1]);
        ans=min(ans,q(*TRE,1,1,n,in[x],out[x])
        +q(TRE[1],1,1,n,in[x],out[x])-2*dep[x]);
    }
    for(auto i:v)upd(*TRE,1,1,n,in[i],1e18);
    for(auto i:v)upd(TRE[1],1,1,n,in[i],1e18);
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'long long int q(long long int*, int, int, int, int, int)':
factories.cpp:10:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |     return min(q(T,i*2,l,l+r>>1,tl,tr),
      |                          ~^~
factories.cpp:11:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |             q(T,i*2+1,l+r+2>>1,r,tl,tr));
      |                       ~~~^~
factories.cpp: In function 'void upd(long long int*, int, int, int, int, long long int)':
factories.cpp:15:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     if(l+r>>1<p)
      |        ~^~
factories.cpp:16:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |         upd(T,i*2+1,l+r+2>>1,r,p,x);
      |                     ~~~^~
factories.cpp:17:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |     else upd(T,i*2,l,l+r>>1,p,x);
      |                      ~^~

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