제출 #881557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881557		Beerus13	공장들 (JOI14_factories)	C++14	0 / 100	55 ms	93008 KiB

factories

#include <bits/stdc++.h>
#include <factories.h>
using namespace std;
#define ll long long
const int ar = 5e5 + 5;
 
int n, q, N, A[ar], B[ar], D[ar], X[ar];
int sz[ar], parent[ar];
multiset<ll> se[ar];
vector<int> adj[ar];
bool deleted[ar];
unordered_map<int, ll> dis[ar];
int vt[ar];
 
void dfs(int u, int par) {
    ++N;
    sz[u] = 1;
    for(auto x : adj[u]) if(x != par && !deleted[x]) {
        dfs(x, u);
        sz[u] += sz[x];
    }
}
 
int find_centroid(int u, int par) {
    for(auto x : adj[u]) if(x != par && !deleted[x] && sz[x] > N / 2) return find_centroid(x, u);
    return u;
}
 
void build_distance(int u, int par, int c, ll d) {
    dis[c][u] = d;
    for(auto x : adj[u]) if(x != par && !deleted[x]) build_distance(x, u, c, d + dis[u][x]);
}
 
void build_tree(int u, int par) {
    N = 0;
    dfs(u, par);
    int centroid = find_centroid(u, par);
    parent[centroid] = par;
    deleted[centroid] = 1;
    build_distance(centroid, par, centroid, 0);
    for(int x : adj[centroid]) if(x != parent[centroid] && !deleted[x]) build_tree(x, centroid);
}
 
void add(int u) {
    for(int par = u; par; par = parent[par]) se[par].insert(dis[par][u]);
}
 
void del(int u) {
    for(int par = u; par; par = parent[par]) se[par].erase(se[par].find(dis[par][u]));
}
 
ll get(int u) {
    ll Min = 1e18;
    for(int par = u; par; par = parent[par]) {
        if(se[par].size()) Min = min(Min, dis[par][u] + *se[par].begin());
    }
    return Min;
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N - 1; ++i) {
        A[i]++; B[i]++;
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
        dis[A[i]][B[i]] = dis[B[i]][A[i]] = D[i];
    }
    build_tree(1, 0);
}

ll Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++)
		add(X[i] + 1);
 
	ll ans = 1e15;
	for (int i = 0; i < T; i++)
		ans = min(ans, get(Y[i] + 1));
 
	for (int i = 0; i < S; i++)
		(X[i] + 1);
	return ans;
} 
 
// int main() {
//     ios::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     cin >> n >> q;
//     for(int i = 0; i < n - 1; ++i) {
//         int x, y, w; cin >> x >> y >> w;
//         x++; y++;
//         adj[x].push_back(y);
//         adj[y].push_back(x);
//         dis[x][y] = dis[y][x] = w;
//     }
//     build_tree(1, 0);
//     while(q--) {
//         int a, b; cin >> a >> b;
//         for(int i = 1; i <= a; ++i) {
//             cin >> vt[i];
//             vt[i]++;
//             add(vt[i]);
//         }
//         ll ans = 1e18;
//         for(int i = 1; i <= b; ++i) {
//             int u; cin >> u;
//             u++;
//             ans = min(ans, get(u));
//         }
//         for(int i = 1; i <= a; ++i) del(vt[i]);
//         cout << ans << '\n';
//     }
// }

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