oj.uz

Submission #881565

# Submission time Handle Problem Language Result Execution time Memory
881565 2023-12-01T13:33:45 Z Beerus13 Factories (JOI14_factories) C++14
0 / 100
 16 ms 43868 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;
    ancestors[centroid].emplace_back(centroid, 0);
    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] = 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:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto [x, w] : adj[centroid]) {
      |              ^
factories.cpp: In function 'void add(int)':
factories.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto [x, w] : ancestors[u]) dp[x] = w;
      |              ^
factories.cpp: In function 'void del(int)':
factories.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for(auto [x, w] : ancestors[u]) dp[x] = inf;
      |              ^
factories.cpp: In function 'long long int get(int)':
factories.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for(auto [x, w] : ancestors[u]) {
      |              ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 43868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 43612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 43868 KB Output isn't correct
2 Halted 0 ms 0 KB -