제출 #364652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364652		bigDuck	공장들 (JOI14_factories)	C++14	18 / 100	8032 ms	117448 KiB

factories

#include "factories.h"

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

int anc[500010][21];



vector<pii> g[500010];
ll d[500010];

int tmp=0;
int ent[500010], ex[500010];


int n;
void dfs(int s){
tmp++;
ent[s]=tmp;
for(pii pr:g[s]){
    int u=pr.ft, c=pr.sc;
    if(u==anc[s][0]){continue;}
    d[u]=d[s]+c;
    anc[u][0]=s;
    dfs(u);
}
tmp++;
ex[s]=tmp;
return;
}


void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0; i<(n-1); i++){
        g[A[i]+1 ].pb({B[i]+1, D[i]});
        g[B[i]+1 ].pb({A[i]+1, D[i]});
    }
    dfs(1);
    for(int i=1; i<=20; i++){
        for(int j=1; j<=n; j++){
            anc[j][i]=anc[anc[j][i-1] ][i-1];
        }
    }
    return;
}


bool is_anc(int u, int v){
    return (ent[u]<=ent[v]) && (ex[u]>=ex[v]);
}



int lca(int u, int v){
if( is_anc(u, v) ){
    return u;
}
int cr=u;

for(int i=20; i>=0; i--){
    if( (anc[cr][i]!=(0)) && (!is_anc(anc[cr][i], v)) ){
        cr=anc[cr][i];
    }
}
return anc[cr][0];
}


bool v[500010];
int mrk[5010];
ll d1[5010];

ll dfs0(int s){
ll res=1e18;
//cout<<"x"<<flush;

if(mrk[s]==1){
    d1[s]=0;
}
else{
        if(d1[s]==0){
    d1[s]=1e18;}
}
//cout<<s<<" "<<mrk[s]<<" "<<d1[s]<<"\n";
v[s]=true;
for(pii pr:g[s]){
    int u=pr.ft, c=pr.sc;
    if(v[u]){continue;}
    res=min(res, dfs0(u));
    d1[s]=min(d1[u]+c, d1[s]);
}
v[s]=false;

v[s]=true;
for(pii pr:g[s]){
    int u=pr.ft, c=pr.sc;
    if(v[u]){continue;}
    d1[u]=min(d1[s]+c, d1[u]);
    res=min(res, dfs0(u));
    d1[s]=min(d1[u]+c, d1[s]);
}
v[s]=false;
if(mrk[s]==2){
    res=min(res, d1[s]);
}
//return res;
return res;
}

long long Query(int S, int X[], int T, int Y[]) {
  ll res=1e18;

  if( n<=5000 ){
    for(int i=0; i<S; i++){
        mrk[X[i]+1 ]=1;
    }
    //ll res=1e18;
    for(int i=0; i<T; i++){
        mrk[Y[i]+1 ]=2;
    }
    //res=min(res, (dfs0(1)).ft);
    ll r=dfs0(1);
    res=min(res, r);
    for(int i=0; i<S; i++){
        mrk[X[i]+1 ]=0;
    }
    //ll res=1e18;
    for(int i=0; i<T; i++){
        mrk[Y[i]+1 ]=0;
    }
    for(int i=1;i<=n; i++){
        d1[i]=0;
    }
  }
  else{


  for(int i=0; i<S; i++){
    for(int j=0; j<T; j++){
        int u=X[i]+1, v=Y[j]+1;
        int anc=lca(u, v);
        res=min(res, d[u]+d[v]-2*d[anc]);
    }
  }
  }
  return res;
}

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