Submission #167543

#	Time	Username	Problem	Language	Result	Execution time	Memory
167543		dessertion	Factories (JOI14_factories)	C++14	100 / 100	6833 ms	261200 KiB

factories

#pragma GCC optimize "O3"
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define pb_ push_back
#define eb_ emplace_back
#define mp_ make_pair
//#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<long,long> pll;
typedef pair<int,int> pii;

const int MN = 5e5+10,LVL=21;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct edge{
    int b,w;
};
vector<edge> adj[MN];
vector<int> adj2[MN];

int sz[MN],tree[MN],depth2[MN],parent[MN][LVL],touched[1000005],eid[MN],revid[MN],efirst[MN],id,cnt,last_touch;
int sparse[LVL][2*MN];
ll dist[MN],ans[MN];
bool done[MN];

int size(int u, int p){
    sz[u] = 1;
    for(auto e : adj[u]){
        if(e.b==p||done[e.b])continue;
        sz[u]+=size(e.b,u);
    }
    return sz[u];
}

int centroid(int u, int p, int tot){
    for(auto e:adj[u])if(e.b!=p&&!done[e.b]&&2*sz[e.b]>=tot)return centroid(e.b,u,tot);
    return u;
}

int decomp(int u, int last){
    int cent = centroid(u,-1,size(u,-1));
    tree[cent]=last;
    done[cent]=1;
    for(auto e : adj[cent]){
        if(done[e.b])continue;
        adj2[cent].pb_(decomp(e.b,cent));
    }
    return cent;
}

void Init(int n, int a[], int b[], int d[]){
    for(int i = 0 ;i < n-1; i++){
        adj[a[i]].pb_({b[i],d[i]});
        adj[b[i]].pb_({a[i],d[i]});
    }
    memset(sparse,0x3f,sizeof(sparse));
    decomp(0,-1);
    function<void(int,int)> dfs = [&](int u, int p){
        eid[u]=++id;
        revid[id]=u;
        efirst[id]=++cnt;
        sparse[0][cnt]=id;
        
        parent[u][0]=p;
        for(auto e : adj[u]){
            if(e.b==p)continue;
            dist[e.b]=e.w+dist[u],depth2[e.b]=depth2[u]+1,dfs(e.b,u);
            sparse[0][++cnt]=eid[u];
        }
    };
    dfs(0,-1);
    for(int i = 1; i < LVL ; i++){
        for(int j = 0; j < n; j++){
            parent[j][i] = parent[parent[j][i-1]][i-1];
        }
    }
    
    /*
    cout<<"SPARSE:\n";
    for(int i = 1; i <= 2*n; i++){
        cout<<sparse[0][i]<<" \n"[i==2*n];
    }
    */
    for(int i = 1; i <= 31-__builtin_clz(2*n); i++){
        for(int j = 1; j +(1<<i)<=2*n; j++){
            sparse[i][j] = min(sparse[i-1][j],sparse[i-1][j+(1<<(i-1))]);
            // cout<<sparse[i][j]<<" \n"[j+(1<<i)==2*n];
        }
    }
    
    memset(ans,0x3f,sizeof(ans));
}

ll getDist(int u, int v){
    /*function<int(int,int)> lca = [&](int a, int b){
        if(depth2[a]>depth2[b])swap(a,b);
        int diff = depth2[b]-depth2[a];
        for(int i =0 ; i < LVL; i++)if((diff>>i)&1)b=parent[b][i];
        if(b==a)return a;
        
        for(int i = LVL-1; i>=0; i--){
            if(parent[a][i]!=parent[b][i])a=parent[a][i],b=parent[b][i];
        }
        return parent[a][0];
    };*/
    function<int(int,int)> lca = [&](int a, int b){
        a=efirst[eid[a]],b=efirst[eid[b]];
        if(a>b)swap(a,b);
        int diff = b-a;
        int lg = 31-__builtin_clz(diff);
        int ret = min(sparse[lg][a],sparse[lg][b-(1<<lg)+1]);
        return revid[ret];
    };
    
    
    int anc = lca(u,v);
    return abs(dist[u]-dist[anc])+abs(dist[v]-dist[anc]);
}

long long Query(int s, int x[], int t, int y[]){
    for(int i = 0 ; i < s ; i++){
        for(int v = x[i]; v!=-1; v=tree[v]){
            ans[v] = min(ans[v],getDist(x[i],v));
            touched[last_touch++]=v;
        }
    }
    ll ret = INF;
    for(int i = 0; i < t; i ++){
        for(int v = y[i]; v!=-1; v=tree[v]){
            ret=min(ret,getDist(v,y[i])+ans[v]);
        }
    }
    for(int i = last_touch-1;i>=0; i--)ans[touched[i]]=INF;
    last_touch=0;
    
    return ret;
}

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