oj.uz

답안 #881560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881560 2023-12-01T13:03:22 Z Beerus13 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 518280 KB 
#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++)
		del(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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 86620 KB Output is correct
2 Correct 1644 ms 102844 KB Output is correct
3 Correct 1851 ms 103060 KB Output is correct
4 Correct 2573 ms 104792 KB Output is correct
5 Correct 2867 ms 104492 KB Output is correct
6 Correct 449 ms 101412 KB Output is correct
7 Correct 1911 ms 103012 KB Output is correct
8 Correct 2109 ms 103264 KB Output is correct
9 Correct 2900 ms 104488 KB Output is correct
10 Correct 455 ms 101544 KB Output is correct
11 Correct 1885 ms 103024 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 86616 KB Output is correct
2 Correct 5488 ms 407416 KB Output is correct
3 Execution timed out 8032 ms 518280 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 86620 KB Output is correct
2 Correct 1644 ms 102844 KB Output is correct
3 Correct 1851 ms 103060 KB Output is correct
4 Correct 2573 ms 104792 KB Output is correct
5 Correct 2867 ms 104492 KB Output is correct
6 Correct 449 ms 101412 KB Output is correct
7 Correct 1911 ms 103012 KB Output is correct
8 Correct 2109 ms 103264 KB Output is correct
9 Correct 2900 ms 104488 KB Output is correct
10 Correct 455 ms 101544 KB Output is correct
11 Correct 1885 ms 103024 KB Output is correct
12 Correct 19 ms 86616 KB Output is correct
13 Correct 5488 ms 407416 KB Output is correct
14 Execution timed out 8032 ms 518280 KB Time limit exceeded
15 Halted 0 ms 0 KB -