oj.uz

Submission #881561

# Submission time Handle Problem Language Result Execution time Memory
881561 2023-12-01T13:04:37 Z Beerus13 Factories (JOI14_factories) C++14
15 / 100
 7538 ms 524288 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
const int ar = 5e5 + 5;
 
int n, q, N;
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

# Verdict Execution time Memory Grader output
1 Correct 43 ms 86896 KB Output is correct
2 Correct 1615 ms 102764 KB Output is correct
3 Correct 1809 ms 102968 KB Output is correct
4 Correct 2436 ms 104736 KB Output is correct
5 Correct 2775 ms 104532 KB Output is correct
6 Correct 441 ms 101544 KB Output is correct
7 Correct 1732 ms 103012 KB Output is correct
8 Correct 1985 ms 103348 KB Output is correct
9 Correct 2719 ms 104476 KB Output is correct
10 Correct 436 ms 101460 KB Output is correct
11 Correct 1807 ms 102992 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 86620 KB Output is correct
2 Correct 5253 ms 406212 KB Output is correct
3 Correct 7538 ms 503912 KB Output is correct
4 Correct 1356 ms 236036 KB Output is correct
5 Runtime error 3565 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 86896 KB Output is correct
2 Correct 1615 ms 102764 KB Output is correct
3 Correct 1809 ms 102968 KB Output is correct
4 Correct 2436 ms 104736 KB Output is correct
5 Correct 2775 ms 104532 KB Output is correct
6 Correct 441 ms 101544 KB Output is correct
7 Correct 1732 ms 103012 KB Output is correct
8 Correct 1985 ms 103348 KB Output is correct
9 Correct 2719 ms 104476 KB Output is correct
10 Correct 436 ms 101460 KB Output is correct
11 Correct 1807 ms 102992 KB Output is correct
12 Correct 19 ms 86620 KB Output is correct
13 Correct 5253 ms 406212 KB Output is correct
14 Correct 7538 ms 503912 KB Output is correct
15 Correct 1356 ms 236036 KB Output is correct
16 Runtime error 3565 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -