Submission #591564

#	Time	Username	Problem	Language	Result	Execution time	Memory
591564		Do_you_copy	Factories (JOI14_factories)	C++17	0 / 100	90 ms	32880 KiB

factories

#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 5e5 + 2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, q;
int a[maxN], b[maxN];
int par[maxN];
int depth[maxN];
int subtree_size[maxN];
ll dist[maxN][20];
ll ans[maxN];
bool visited[maxN];
vector <pii> adj[maxN];

void centroid_dfs(int u, int p){
    subtree_size[u] = 1;
    for (const auto &i: adj[u]){
        if (visited[i.fi] || i.fi == p) continue;
        centroid_dfs(i.fi, u);
        subtree_size[u] += subtree_size[i.fi];
    }
}

int find_centroid(int u, int p, int sz){
    for (const auto &i: adj[u]){
        if (visited[i.fi] || i.fi == p) continue;
        if (subtree_size[i.fi] > sz / 2) return find_centroid(i.fi, u, sz);
    }
    return u;
}

void find_distance(int u, int p, int c, ll d = 0){
    for (const auto &i: adj[u]){
        if (visited[i.fi] || i.fi == p) continue;
        dist[i.fi][c] = d + i.se;
        find_distance(i.fi, u, c, d + i.se);
    }
}

void update(int u){
    int v = u;
    while (v){
        ans[v] = min(ans[v], dist[u][depth[v]]);
        v = par[v];
    }
}

ll get(int u){
    ll res = inf;
    int v = u;
    while (v){
        res = min(res, ans[v] + dist[u][depth[v]]);
        v = par[v];
    }
    return res;
}

void reupdate(int u){
    int v = u;
    while (v){
        ans[v] = inf;
        v = par[v];
    }
}
int build_centroid(int u, int low){
    centroid_dfs(u, -1);
    int centroid = find_centroid(u, -1, subtree_size[u]);
    visited[centroid] = 1;
    depth[centroid] = low;
    find_distance(centroid, -1, low);
    for (const auto &i: adj[centroid]){
        if (visited[i.fi]) continue;
        par[build_centroid(i.fi, low + 1)] = centroid;
    }
    return centroid;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    memset(ans, 0x3f, sizeof(ans));
    for (int i = 0; i < n - 1; ++i){
        int u, v, w;
        u = A[i], v = B[i], w = D[i];
        adj[u + 1].pb({v + 1, w});
        adj[v + 1].pb({u + 1, w});
    }
    par[build_centroid(1, 1)] = 0;
}

ll Query(int S, int X[], int T, int Y[]){
    for (int i = 0; i < S; ++i){
        update(X[i] + 1);
    }
    ll answer = inf;
    for (int i = 0; i < T; ++i){
        answer = min(answer, get(Y[i] + 1));
    }
    for (int i = 0; i < S; ++i){
        reupdate(X[i] + 1);
    }
    cout << answer << "\n";
}

Compilation message (stderr)

factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:126:1: warning: no return statement in function returning non-void [-Wreturn-type]
  126 | }
      | ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67