Submission #153973

#	Time	Username	Problem	Language	Result	Execution time	Memory
153973		Mercenary	Factories (JOI14_factories)	C++14	100 / 100	7870 ms	315872 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 big[maxn] , vis[maxn] , n , sub[maxn];
ll dep[maxn] , cen[maxn];

vector<int> v[maxn];
vector<ii> adj[maxn];
vector<ll> predis[maxn];

void DFS(int u , int v){
    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){
    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);
    vis[u] = 1;
    function<void(int,int,ll dep)> DFS = [&](int uu , int v , ll dep){
        ::v[uu].pb(u);
        predis[uu].pb(dep);
        for(ii c : adj[uu]){
            if(c.first != v && vis[c.first] == 0){
                DFS(c.first , uu , dep + c.second);
            }
        }
    };
    DFS(u , -1 , 0);
    for(auto& c : adj[u]){
        if(vis[c.first] == 0){
            Decompose(c.first);
        }
    }
}

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]));
    }
    Decompose(0);
    for(int i = 0 ; i < n ; ++i)cen[i] = 1e18;
}

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: 18 / 18
• Subtask 3: 67 / 67