Submission #153972

#	Time	Username	Problem	Language	Result	Execution time	Memory
153972		Mercenary	Factories (JOI14_factories)	C++14	15 / 100	8042 ms	347092 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;
const int maxn = 5e5 + 5;
const int logn = log2(maxn) + 1;
typedef pair<int,int> ii;
typedef long long ll;

int h[maxn] , P[maxn][logn];
int big[maxn] , vis[maxn] , n , sub[maxn];
ll dep[maxn] , cen[maxn];

vector<int> v[maxn] , now;
vector<ii> adj[maxn];

void DFS(int u , int v){
    now.pb(u);
    sub[u] = 1;
    big[u] = -1;
    for(auto& c : adj[u]){
        if(c.first != v && vis[c.first] == 0){
            DFS(c.first , u);
            sub[u] += sub[c.first];
            if(big[u] == -1 || sub[big[u]] < sub[c.first])big[u] = c.first;
        }
    }
}

int FindRoot(int u){
    now.clear();
    DFS(u , -1);
    int total = sub[u];
    while(big[u] != -1 && sub[big[u]] * 2 >= total)u = big[u];
    return u;
}

void Decompose(int u){
    u = FindRoot(u);
    for(int & c : now)v[c].pb(u);
    vis[u] = 1;
    for(auto& c : adj[u]){
        if(vis[c.first] == 0){
            Decompose(c.first);
        }
    }
}

int LCA(int u , int v){
    if(h[u] < h[v])swap(u , v);
    for(int i = 0 ; i < logn && h[u] != h[v]  ; ++i){
        if((h[u] - h[v]) & (1 << i))u = P[u][i];
    }
    if(u == v)return u;
    for(int i = logn - 1 ; i >= 0 ; --i){
        if(P[u][i] != P[v][i]){
            u = P[u][i];
            v = P[v][i];
        }
    }
    return P[u][0];
}

ll dis(int u , int v){
    return dep[u] + dep[v] - 2 * dep[LCA(u , v)];
}

vector<ll> predis[maxn];

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0 ; i < n - 1 ; ++i){
        adj[A[i]].pb(mp(B[i] , D[i]));
        adj[B[i]].pb(mp(A[i] , D[i]));
    }
    function<void(int,int)> DFS = [&](int u , int v){
        for(auto & c : adj[u]){
            if(c.first != v){
                h[c.first] = h[u] + 1;
                dep[c.first] = dep[u] + c.second;
                P[c.first][0] = u;
                for(int i = 1 ; i < logn && P[c.first][i - 1] != -1 ; ++i){
                    P[c.first][i] = P[P[c.first][i - 1]][i - 1];
                }
                DFS(c.first , u);
            }
        }
    };
    memset(P,-1,sizeof P);
    DFS(0 , -1);
    Decompose(0);
    for(int i = 0 ; i < n ; ++i)cen[i] = 1e18;
    for(int i = 0 ; i < n ; ++i){
        for(int & c : v[i]){
            predis[i].pb(dis(c , i));
        }
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    ll total = 1e18;
    for(int i = 0 ; i < S ; ++i){
        for(int j = (int)v[X[i]].size() -1; j >= 0 ; --j){
            cen[v[X[i]][j]] = min(cen[v[X[i]][j]] , predis[X[i]][j]);
        }
    }
    for(int i = 0 ; i < T ; ++i){
        ll res = 1e18;
        for(int j = (int)v[Y[i]].size() -1; j >= 0 ; --j){
             res = min(res , predis[Y[i]][j] + cen[v[Y[i]][j]]);
        }
        total = min(total , res);
    }
    for(int i = 0 ; i < S ; ++i){
        for(int c : v[X[i]]){
            cen[c] = 1e18;
        }
    }
    return total;
}

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