제출 #1316616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316616		wangzhiyi33	공장들 (JOI14_factories)	C++20	0 / 100	2316 ms	350528 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ii pair<ll,ll>
#define fir first
#define sec second
#define pb push_back

const int maxn=5e5;
int n;
vector<ii>adj[maxn+2];
ll sub[maxn+2];
bool vis[maxn+2];

void dfs(int cur,int par){
    sub[cur]=1;
    for(auto [x,di] : adj[cur]){
      if(x==par)continue;
      if(vis[x]){
        sub[x]=0; continue;
      }
      dfs(x,cur);
      sub[cur]+=sub[x];
    }
}

int centro(int cur,int par,int sz){
    for(auto [x,di] : adj[cur]){
      if(x==par || vis[x])continue;
      if(sub[x]>=sz/2){
        return centro(x,cur,sz);
      }
    }

    return cur;
}

vector<ii>anc[maxn+2];
void comp(int cur,int par,int root,ll tot){
    anc[cur].pb({tot,root});
    for(auto [x,di] : adj[cur]){
      if(x==par || vis[x])continue;
      comp(x,cur,root,tot+di);
    }
}

void solve(int cur){
  dfs(cur,0);
  int root=centro(cur,0,sub[cur]);

  comp(root,0,root,0);
  vis[root]=true;
  for(auto [x,di] : adj[root]){
    if(vis[x])continue;
    solve(x);
  }
}

ll dkt[maxn+2];
void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int q=0;q<n-1;q++){
      adj[A[q]].pb({B[q],D[q]});
      adj[B[q]].pb({A[q],D[q]});
    }
    solve(1);
    for(int q=0;q<N;q++)dkt[q]=1e18;
}

void update(int idx){
  for(auto [tot,root] : anc[idx]){
    //cout<<idx<<" "<<tot<<" "<<root<<endl;
    dkt[root]=min(dkt[root],tot);
  }
}

void reset(int idx){
  for(auto [tot,root] : anc[idx]){
    dkt[root]=1e18;
  }
}

ll query(int idx){
  ll ans=1e18;
  for(auto [tot,root] : anc[idx]){
    //cout<<idx<<" "<<tot<<" "<<root<<" "<<dkt[root]<<endl;
    ans=min(ans,tot+dkt[root]);
  }
  return ans;
}

ll Query(int S, int X[], int T, int Y[]) {
  for(int q=0;q<S;q++){
    update(X[q]);
  }
  ll ans=1e18;
  for(int q=0;q<T;q++){
    ans=min(ans,query(Y[q]));
  }
  for(int q=0;q<S;q++){
    reset(X[q]);
  }
  return ans;
}

// signed main(){
//   int N,qu;
//   cin>>N>>qu;
//   int A[N],B[N],D[N];
//   for(int q=0;q<N-1;q++){
//     cin>>A[q]>>B[q]>>D[q];
//   }
//   Init(N,A,B,D);
//   for(int q=0;q<N;q++){
//     cout<<vis[q]<<" ";
//   }
//   cout<<endl;

//   while(qu--){
//     int S,T;
//     cin>>S>>T;
//     int X[S],Y[T];
//     for(int q=0;q<S;q++)cin>>X[q];
//     for(int q=0;q<T;q++)cin>>Y[q];
//     cout<<Query(S,X,T,Y)<<endl;
//   }
// }

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