oj.uz

Submission #881573

# Submission time Handle Problem Language Result Execution time Memory
881573 2023-12-01T14:04:40 Z Beerus13 Factories (JOI14_factories) C++14
100 / 100
 3668 ms 380944 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, A[ar], B[ar], D[ar], Y[ar], X[ar], S, T;
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 12 ms 45660 KB Output is correct
2 Correct 194 ms 59364 KB Output is correct
3 Correct 204 ms 59984 KB Output is correct
4 Correct 208 ms 59880 KB Output is correct
5 Correct 215 ms 60244 KB Output is correct
6 Correct 150 ms 58996 KB Output is correct
7 Correct 225 ms 59740 KB Output is correct
8 Correct 210 ms 59988 KB Output is correct
9 Correct 224 ms 60380 KB Output is correct
10 Correct 148 ms 58852 KB Output is correct
11 Correct 202 ms 59924 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 1787 ms 226420 KB Output is correct
3 Correct 2597 ms 300076 KB Output is correct
4 Correct 632 ms 118464 KB Output is correct
5 Correct 3306 ms 380944 KB Output is correct
6 Correct 2677 ms 301036 KB Output is correct
7 Correct 699 ms 100240 KB Output is correct
8 Correct 252 ms 76224 KB Output is correct
9 Correct 746 ms 112688 KB Output is correct
10 Correct 706 ms 100708 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 45660 KB Output is correct
2 Correct 194 ms 59364 KB Output is correct
3 Correct 204 ms 59984 KB Output is correct
4 Correct 208 ms 59880 KB Output is correct
5 Correct 215 ms 60244 KB Output is correct
6 Correct 150 ms 58996 KB Output is correct
7 Correct 225 ms 59740 KB Output is correct
8 Correct 210 ms 59988 KB Output is correct
9 Correct 224 ms 60380 KB Output is correct
10 Correct 148 ms 58852 KB Output is correct
11 Correct 202 ms 59924 KB Output is correct
12 Correct 9 ms 45660 KB Output is correct
13 Correct 1787 ms 226420 KB Output is correct
14 Correct 2597 ms 300076 KB Output is correct
15 Correct 632 ms 118464 KB Output is correct
16 Correct 3306 ms 380944 KB Output is correct
17 Correct 2677 ms 301036 KB Output is correct
18 Correct 699 ms 100240 KB Output is correct
19 Correct 252 ms 76224 KB Output is correct
20 Correct 746 ms 112688 KB Output is correct
21 Correct 706 ms 100708 KB Output is correct
22 Correct 1977 ms 231200 KB Output is correct
23 Correct 2064 ms 235036 KB Output is correct
24 Correct 3159 ms 304172 KB Output is correct
25 Correct 3197 ms 307312 KB Output is correct
26 Correct 3017 ms 306244 KB Output is correct
27 Correct 3668 ms 380164 KB Output is correct
28 Correct 703 ms 128684 KB Output is correct
29 Correct 3056 ms 305168 KB Output is correct
30 Correct 3051 ms 304536 KB Output is correct
31 Correct 3062 ms 304996 KB Output is correct
32 Correct 931 ms 113324 KB Output is correct
33 Correct 245 ms 76124 KB Output is correct
34 Correct 491 ms 93136 KB Output is correct
35 Correct 498 ms 93776 KB Output is correct
36 Correct 674 ms 99156 KB Output is correct
37 Correct 683 ms 99412 KB Output is correct