oj.uz

Submission #881575

# Submission time Handle Problem Language Result Execution time Memory
881575 2023-12-01T14:07:40 Z Beerus13 Factories (JOI14_factories) C++14
100 / 100
 3693 ms 377376 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define pii pair<int, ll>
const int ar = 5e5 + 5;
const ll inf = 1e15;
 
int n, q, N;
int sz[ar], vt[ar];
vector<pii> adj[ar], ancestors[ar];
bool deleted[ar];
ll dp[ar];
 
void dfs(int u, int par) {
    ++N;
    sz[u] = 1;
    for(auto [x, w] : adj[u]) if(x != par && !deleted[x]) {
        dfs(x, u);
        sz[u] += sz[x];
    }
}
 
int find_centroid(int u, int par) {
    for(auto [x, w] : 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) {
    for(auto [x, w] : adj[u]) if(x != par && !deleted[x]) build_distance(x, u, c, d + w);
    ancestors[u].emplace_back(c, d);
}
 
void build_tree(int u) {
    N = 0;
    dfs(u, u);
 
    int centroid = find_centroid(u, u);
    deleted[centroid] = 1;
    build_distance(centroid, centroid, centroid, 0);
    for(auto [x, w] : adj[centroid]) {
        if(!deleted[x]) build_tree(x);
    }
}
 
void add(int u) {
    for(auto [x, w] : ancestors[u]) dp[x] = min(dp[x], w);
}
 
void del(int u) {
    for(auto [x, w] : ancestors[u]) dp[x] = inf;
}
 
ll get(int u) {
    ll ans = inf;
    for(auto [x, w] : ancestors[u]) {
        ans = min(ans, w + dp[x]);
    }
    return ans;
}
 
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]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    for(int i = 1; i <= N; ++i) dp[i] = inf;
    build_tree(1);
}
 
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;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:18:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for(auto [x, w] : adj[u]) if(x != par && !deleted[x]) {
      |              ^
factories.cpp: In function 'int find_centroid(int, int)':
factories.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for(auto [x, w] : adj[u]) if(x != par && !deleted[x] && sz[x] > N / 2) return find_centroid(x, u);
      |              ^
factories.cpp: In function 'void build_distance(int, int, int, long long int)':
factories.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [x, w] : adj[u]) if(x != par && !deleted[x]) build_distance(x, u, c, d + w);
      |              ^
factories.cpp: In function 'void build_tree(int)':
factories.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [x, w] : adj[centroid]) {
      |              ^
factories.cpp: In function 'void add(int)':
factories.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto [x, w] : ancestors[u]) dp[x] = min(dp[x], w);
      |              ^
factories.cpp: In function 'void del(int)':
factories.cpp:51:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto [x, w] : ancestors[u]) dp[x] = inf;
      |              ^
factories.cpp: In function 'long long int get(int)':
factories.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [x, w] : ancestors[u]) {
      |              ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 45648 KB Output is correct
2 Correct 303 ms 59432 KB Output is correct
3 Correct 221 ms 59860 KB Output is correct
4 Correct 210 ms 59728 KB Output is correct
5 Correct 228 ms 60456 KB Output is correct
6 Correct 147 ms 58848 KB Output is correct
7 Correct 208 ms 59728 KB Output is correct
8 Correct 212 ms 59988 KB Output is correct
9 Correct 216 ms 60268 KB Output is correct
10 Correct 147 ms 58964 KB Output is correct
11 Correct 216 ms 59988 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45660 KB Output is correct
2 Correct 1791 ms 223328 KB Output is correct
3 Correct 2719 ms 294828 KB Output is correct
4 Correct 621 ms 119004 KB Output is correct
5 Correct 3304 ms 377376 KB Output is correct
6 Correct 2673 ms 296944 KB Output is correct
7 Correct 683 ms 98796 KB Output is correct
8 Correct 241 ms 74688 KB Output is correct
9 Correct 800 ms 111016 KB Output is correct
10 Correct 710 ms 99132 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 45648 KB Output is correct
2 Correct 303 ms 59432 KB Output is correct
3 Correct 221 ms 59860 KB Output is correct
4 Correct 210 ms 59728 KB Output is correct
5 Correct 228 ms 60456 KB Output is correct
6 Correct 147 ms 58848 KB Output is correct
7 Correct 208 ms 59728 KB Output is correct
8 Correct 212 ms 59988 KB Output is correct
9 Correct 216 ms 60268 KB Output is correct
10 Correct 147 ms 58964 KB Output is correct
11 Correct 216 ms 59988 KB Output is correct
12 Correct 9 ms 45660 KB Output is correct
13 Correct 1791 ms 223328 KB Output is correct
14 Correct 2719 ms 294828 KB Output is correct
15 Correct 621 ms 119004 KB Output is correct
16 Correct 3304 ms 377376 KB Output is correct
17 Correct 2673 ms 296944 KB Output is correct
18 Correct 683 ms 98796 KB Output is correct
19 Correct 241 ms 74688 KB Output is correct
20 Correct 800 ms 111016 KB Output is correct
21 Correct 710 ms 99132 KB Output is correct
22 Correct 2122 ms 226856 KB Output is correct
23 Correct 2134 ms 230688 KB Output is correct
24 Correct 3181 ms 297064 KB Output is correct
25 Correct 3178 ms 303116 KB Output is correct
26 Correct 2966 ms 301516 KB Output is correct
27 Correct 3693 ms 375548 KB Output is correct
28 Correct 736 ms 124588 KB Output is correct
29 Correct 2917 ms 300608 KB Output is correct
30 Correct 2890 ms 300388 KB Output is correct
31 Correct 3076 ms 298000 KB Output is correct
32 Correct 932 ms 112044 KB Output is correct
33 Correct 241 ms 74892 KB Output is correct
34 Correct 513 ms 91728 KB Output is correct
35 Correct 583 ms 92500 KB Output is correct
36 Correct 720 ms 97784 KB Output is correct
37 Correct 746 ms 98084 KB Output is correct