Submission #1127064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127064		Ludissey	Factories (JOI14_factories)	C++20	100 / 100	6791 ms	439420 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
 
vector<vector<pair<int,int>>> neigh;
vector<pair<int,int>> parent;
vector<vector<int>> parent2;
vector<vector<pair<int,int>>> parents;
vector<int> childC;
vector<int> cindx;
vector<int> depth;
vector<int> depthD;
vector<int> ans;
int n;
int K;
int ct=0;
int _n=0;
int solu=1e18;
const int LOG=18;


int build_tree(int x, int p){
    childC[x]=1;
    for (int t=0; t<sz(neigh[x]); t++)
    {
        int u=neigh[x][t].first;
        if(u==p||cindx[u]>=0) continue;
        childC[x]+=build_tree(u,x);
    }
    return childC[x];
}
 
pair<int,int> centroid(int x, int p){
    for (int t=0; t<sz(neigh[x]); t++)
    {
        int u=neigh[x][t].first;
        if(u==p||cindx[u]>=0) continue;
        if(childC[u]*2>=_n) {
            pair<int,int> c=centroid(u,x);
            return {c.first,c.second+neigh[x][t].second};
        }
    }
    return {x,0};
}

pair<int,int> decompo(int x, int compoINDEX){
    build_tree(x,-1);
    _n=childC[x];
    pair<int,int> c=centroid(x,-1);
    cindx[c.first]=compoINDEX;
    for (auto u : neigh[c.first])
    {
        if(cindx[u.first]>=0) continue;
        pair<int,int> dc=decompo(u.first,compoINDEX+1);
        parent[dc.first]={c.first,dc.second+u.second};
    }
    return c;
}
 

 
void build_lca(int x, int p, int dp, int dp2){
    depth[x]=dp;
    depthD[x]=dp2;
    for (int t=0; t<sz(neigh[x]); t++)
    {
        int u=neigh[x][t].first;
        if(u==p) continue;
        build_lca(u,x,dp+1,dp2+neigh[x][t].second);
        parent2[u][0]=x;
    }
    return;
}

void lca_prep(){
    for (int j = 1; j < LOG; j++)
    {
        for (int i = 0; i < n; i++)
        {
            parent2[i][j]=parent2[parent2[i][j-1]][j-1];
        }
    }
}

int lca(int a, int b){
    if(depth[b]<depth[a]) swap(a,b);
    int d=depth[b]-depth[a];
    for (int j = LOG-1; j >= 0;j--)
    {
        if(d&(1<<j)) b=parent2[b][j];
    }
    if(a==b) return a;
    for (int j = LOG-1; j >= 0;j--)
    {
        if(parent2[a][j]!=parent2[b][j]) {
            a=parent2[a][j];
            b=parent2[b][j];
        }
    }
    return parent2[a][0];
}

int dist(int a, int b){
    return depthD[a]+depthD[b]-2*depthD[lca(a,b)];
}

void update(int x){
  ans[x]=0;
  for (auto u: parents[x])
  {
    ans[u.first]=min(ans[u.first],u.second);
  }
}

int query(int x){
  int mn=ans[x];
  for (auto u: parents[x])
  {
    mn=min(ans[u.first]+u.second,mn);
  }
  return mn;
}

void clear(int x){
  ans[x]=1e18;
  for (auto u: parents[x])
  {
    ans[u.first]=1e18;
  }
}

void Init(signed N, signed A[], signed B[], signed D[]) {
    n=N;
    neigh.resize(n);
    cindx.resize(n);
    childC.resize(n,0);
    depth.resize(n,0);
    parents.resize(n);
    depthD.resize(n,0);
    parent.resize(n,{-1,-1});
    parent2.resize(n,vector<int>(LOG,0));
    ans.resize(n,1e18);
    for (int i = 0; i < n-1; i++)
    {
        int a=A[i],b=B[i];
        neigh[a].push_back({b,D[i]});
        neigh[b].push_back({a,D[i]});
    }
    cindx.clear(); cindx.resize(n,-1);
    childC.resize(n);
    build_lca(0,-1,0,0);
    parent2[0][0]=0;
    lca_prep();
    decompo(0,0);
    for (int i = 0; i < n; i++)
    {
      int u=parent[i].first;
      while(u!=-1){
        parents[i].push_back({u,dist(i,u)});
        u=parent[u].first;
      }
    }
    
}

long long Query(signed S, signed X[], signed T, signed Y[]) {
    int mn=1e18;
    for (int i = 0; i < S; i++)
    {
      update(X[i]);
    }
    for (int i = 0; i < T; i++)
    {
      mn=min(mn,query(Y[i]));
    }
    for (int i = 0; i < S; i++)
    {
      clear(X[i]);
    }
    return mn;
}

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