Submission #419086

#	Time	Username	Problem	Language	Result	Execution time	Memory
419086		ak2006	Factories (JOI14_factories)	C++14	0 / 100	6348 ms	118460 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
int n = 5e5 + 5,m,timer = 0;
vector<set<pair<int,int>>>adj(n);
vi sub(n),par(n,-1),in(n),out(n);
vl d(n),res(n,inf);
vi when(n);
int queryNumber;
vvi dp(n,vi(21,1));
 
void orig_dfs(int i,int p,ll w)
{
    if (p != -1)d[i] = d[p] + w;
    if (p != -1)dp[i][0] = p;
    for (int power = 1;power<=20;power++)dp[i][power] = dp[dp[i][power - 1]][power - 1];
    in[i] = ++timer;
    for (auto val:adj[i]){
        int c = val.first;
        ll wt = val.second;
        if (c != p)orig_dfs(c,i,wt);
    }
    out[i] = ++timer;
}
bool is_anc(int i,int j)
{
    return in[i] <= in[j] && out[i] >= out[j];
}
int lca(int i,int j)
{
    if (in[i] > in[j])swap(i,j);
    int ret = j;
    for (int power = 20;power >= 0;power--){
        if (!is_anc(dp[ret][power],i))ret = dp[ret][power];
    }
    if (i == j)return i;
    return dp[ret][0];
}
ll dist(int i,int j)
{
    if (in[i] > in[j])swap(i,j);
    int l = lca(i,j);
    if (is_anc(i,j))return d[j] - d[i];
    return d[i] + d[j] - 2 * d[l];
}
int dfs(int i,int p)
{
    sub[i] = 1;
    for (auto val:adj[i]){
        int c = val.first;
        if (c != p)sub[i] += dfs(c,i);
    }
    return sub[i];
}
int centroid(int i,int p,int sz)
{
    for (auto val:adj[i]){
        int c = val.first;
        if (c != p && sub[c] > sz/2)return centroid(c,i,sz);
    }
    return i;
}
void decompose(int i,int p,ll w)
{
    int cent = centroid(i,p,dfs(i,-1));
    par[cent] = p;
    for (auto val:adj[cent]){
        int nxt = val.first;
        ll wt = val.second;
        adj[nxt].erase({cent,wt});
        decompose(nxt,cent,wt);
    }
}
void update(int i)
{
    int cur = i;
    while (cur != -1){
        res[cur] = min(res[cur],dist(cur,i));
        when[cur] = queryNumber;
        cur = par[cur];
    }
}
ll query(int i)
{
    ll ret = inf;
    int cur = i;
    while (cur != -1){
        ret = min(ret,dist(cur,i) + res[cur]);
        cur = par[cur];
    }
    return ret;
}
void reset(int i)
{
    while (i != -1){
        res[i] = inf;
        i = par[i];
    }
}
 
void Init(int N, int a[], int b[], int d[]) {
  n = N;
  for (int i = 0;i<n - 1;i++){
    int u = a[i],v = b[i],w = d[i];
    u++,v++;
    adj[u].insert({v,w}),adj[v].insert({u,w});
  }
  orig_dfs(1,-1,0);
    decompose(1,-1,0);
    update(1);
}
 
long long Query(int a, int v1[], int b, int v2[]) {
  ll ans = inf;
  for (int i = 0;i<a;i++)update(v1[i] + 1);
  for (int i = 0;i<b;i++)ans = min(ans,query(v2[i] + 1));
  for (int i = 0;i<a;i++)reset(v1[i] + 1);
  return ans;
}
// int main()
// {
//     fast;
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
//     cin>>n>>m;
//     for (int i = 0;i<n - 1;i++){int u,v,w;cin>>u>>v>>w;u++,v++;adj[u].insert({v,w}),adj[v].insert({u,w});}
//     orig_dfs(1,-1,0);
//     decompose(1,-1,0);
//     update(1);
//     while (m--){
//         queryNumber++;
//         int a,b;
//         cin>>a>>b;
//         ll ans = inf;
//         vi all;
//         for (int i = 1;i<=a;i++){int x;cin>>x;x++;update(x);all.pb(x);}
//         for (int i = 1;i<=b;i++){int x;cin>>x;x++;ans = min(ans,query(x));}
//         for (auto it:all)reset(it);
//         cout<<ans<<'\n';
//     }
//     return 0;
// }

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