Submission #464595

#	Time	Username	Problem	Language	Result	Execution time	Memory
464595		TruaShamu	공장들 (JOI14_factories)	C++11	100 / 100	5543 ms	371832 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<ll, ll> pii;

const int MAXN = 5e5 + 5;

ll sub_size[MAXN], visited[MAXN], best[MAXN];
vector<pii> adj[MAXN], dis[MAXN];

// Find subtree size.
int subSize(int cur, int par) {
    sub_size[cur] = 1;
    for (pii next : adj[cur])
        if (next.f != par && !visited[next.f])
            sub_size[cur] += subSize(next.f, cur);
    return sub_size[cur];
}
// Return the centroid.
int findCentroid(int cur, int par, int N) {
    for (pii next : adj[cur]) {
        if (next.f != par && !visited[next.f] && sub_size[next.f] > N / 2) {
            return findCentroid(next.f, cur, N);
        }
    }
    return cur;
}

void getDis(int cur, int par, int c, ll dist) {
    dis[cur].pb({ c, dist });
    for (pii next : adj[cur]) {
        if (next.f != par && !visited[next.f]) {
            getDis(next.f, cur, c, dist + next.s);
        }
    }
}

void build(int cur) {
    int centroid = findCentroid(cur, -1, subSize(cur, -1));
    getDis(centroid, -1, centroid, 0);
    visited[centroid] = 1;

    for (pii next : adj[centroid]) {
        if (!visited[next.f]) {
            build(next.f);
        }
    }
}



// Initialize function
void Init(int n, int a[], int b[], int c[]) {
    // Read edges
    for (int i = 0; i < n - 1; i++) {
        adj[a[i]].pb({ b[i], c[i] });
        adj[b[i]].pb({ a[i], c[i] });
    }
    build(0);
    fill(best, best + MAXN, LINF);
}

// Process queries
ll Query(int len1, int x[], int len2, int y[]) {

    ll ans = LINF;
    for (int u = 0; u < len1; u++) {
        for (pii i : dis[x[u]]) {
            best[i.f] = min(best[i.f], i.s);
        }
    }
    for (int u = 0; u < len2; u++) {
        for (pii i : dis[y[u]]) {
            ans = min(ans, best[i.f] + i.s);
        }
    }
    for (int u = 0; u < len1; u++) {
        for (pii i : dis[x[u]]) {
            best[i.f] = LINF;
        }
    }
    return ans;
}

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