Submission #335656

#	Time	Username	Problem	Language	Result	Execution time	Memory
335656		Joshc	Factories (JOI14_factories)	C++11	0 / 100	46 ms	24556 KiB

factories

#include "factories.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define ll long long
#define pli pair<ll, int>
#define f first
#define s second

const int MAX_N = 500001;

vector<pli> edges[MAX_N], edges2[MAX_N];
int jump[MAX_N][19], order[MAX_N], depth[MAX_N], timer = 0;
ll dist[MAX_N], dist2[MAX_N];

void dfs(int v, int p, int d) {
    jump[v][0] = p;
    for (int i=1; i<19; i++) jump[v][i] = jump[jump[v][i-1]][i-1];
    order[v] = ++timer;
    depth[v] = d;
    for (pli u : edges[v]) {
        if (u.f != p) {
            dist[u.f] = dist[v]+u.s;
            dfs(u.f, v, d+1);
        }
    }
}

int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    int z = depth[x]-depth[y];
    for (int i=18; i>=0; i--) {
        if (z&(1<<i)) x = jump[x][i];
    }
    if (x == y) return x;
    for (int i=18; i>=0; i--) {
        if (jump[x][i] != jump[y][i]) {
            x = jump[x][i];
            y = jump[y][i];
        }
    }
    return jump[x][0];
}

ll distance(int x, int y) {
    return dist[x]+dist[y]-2*dist[lca(x, y)];
}

void add(int a, int b, ll c, vector<pli> edges[]) {
    edges[a].emplace_back(b, c);
    edges[b].emplace_back(a, c);
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i=0; i<N-1; i++) add(A[i]+1, B[i]+1, D[i], edges);
    dfs(1, 0, 0);
    for (int i=1; i<=N; i++) dist2[i] = 1e18;
}

bool comp(int x, int y) {
    return order[x] < order[y];
}

void clean(int x) {
    dist2[x] = 1e18;
    edges2[x].clear();
}

ll Query(int S, int X[], int T, int Y[]) {
    vector<int> v, l;
    for (int i=0; i<S; i++) v.push_back(++X[i]);
    for (int i=0; i<T; i++) v.push_back(++Y[i]);
    sort(v.begin(), v.end(), comp);
    for (int i=0; i<S+T-1; i++) {
        int cur = lca(v[i], v[i+1]);
        add(v[i], cur, dist[v[i]]-dist[cur], edges2);
        add(v[i+1], cur, dist[v[i+1]]-dist[cur], edges2);
        l.push_back(cur);
    }
    sort(l.begin(), l.end(), comp);
    for (int i=0; i<S+T-2; i++) add(l[i], l[i+1], distance(l[i], l[i+1]), edges2);
    priority_queue<pli, vector<pli>, greater<pli> > pq;
    for (int i=0; i<S; i++) {
        dist2[X[i]] = 0;
        pq.push({0, X[i]});
    }
    while (!pq.empty()) {
        pli cur = pq.top();
        pq.pop();
        if (cur.f > dist[cur.s]) continue;
        for (pli p : edges2[cur.s]) {
            if (dist2[p.f] > cur.f+p.s) {
                dist2[p.f] = cur.f+p.s;
                pq.push({dist2[p.f], p.f});
            }
        }
    }
    ll ans = 1e18;
    for (int i=0; i<T; i++) ans = min(ans, dist2[Y[i]]);
    for (int i=0; i<S; i++) clean(X[i]);
    for (int i=0; i<T; i++) clean(Y[i]);
    for (int i : l) clean(i);
    return ans;
}

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