제출 #1144669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144669		Newtonabc	공장들 (JOI14_factories)	C++20	100 / 100	3796 ms	350188 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const int M=5e5+10;
bool rem[M];
vector<pair<int,long long>> adj[M],dc[M];
long long dist[M];
int upd[M];
//dist to centroid {centroid,dist}
int sz[M],t=1;

void findsz(int u,int p=-1){
  sz[u]=1;
  for(auto [v,w]:adj[u]){
    if(v==p || rem[v]) continue;
    findsz(v,u);
    sz[u]+=sz[v];
  }
}

void dfs(int u,int p,int ed,long long d=0){
  dc[u].push_back({ed,d});
  for(auto [v,w]:adj[u]){
    if(v==p || rem[v]) continue;
    dfs(v,u,ed,d+w);
  }
}

int cen(int u,int treesz,int p=-1){
  for(auto [v,w]:adj[u]){
    if(v==p || rem[v]) continue;
    if(sz[v]*2>treesz) return cen(v,treesz,u);
  }
  return u;
}

void decom(int u){
  findsz(u);
  int c=cen(u,sz[u]);
  dfs(c,-1,c);
  //now parent centroid
  rem[c]=true;
  for(auto [v,w]:adj[c]){
    if(rem[v]) continue;
    decom(v);
  }
}

void Init(int N, int A[], int B[], int D[]) {
  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]});
  }
  decom(0);
  /*for(int i=0;i<N;i++){
    cout<<i <<"\n";
    for(auto [cen,d]:dc[i]){
      cout<<cen <<" " <<d <<"\n";
    }
  }*/
}

long long Query(int S, int X[], int T, int Y[]){
  for(int i=0;i<S;i++){
    int u=X[i];
    for(auto [cen,d]:dc[u]){
      if(upd[cen]!=t){
        upd[cen]=t;
        dist[cen]=d;
      }
      else{
        dist[cen]=min(dist[cen],d);
      }
    }
  }
  long long ans=LLONG_MAX;
  for(int i=0;i<T;i++){
    int u=Y[i];
    for(auto [cen,d]:dc[u]){
      if(upd[cen]!=t) continue;
      ans=min(ans,dist[cen]+d);
    }
  }
  t++;
  return ans;
}

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