oj.uz

Submission #895488

# Submission time Handle Problem Language Result Execution time Memory
895488 2023-12-30T03:42:56 Z 12345678 Factories (JOI14_factories) C++17
100 / 100
 3177 ms 210308 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=5e5+5, kx=21;
ll ds[kx][nx], c[nx], sz[nx], dp[nx], lvl[nx];
vector<pair<ll, ll>> d[nx];
bool used[nx];
vector<ll> rem;


int dfssz(int u, int p)
{
    sz[u]=1;
    for (auto [v, w]:d[u]) if (v!=p&&!used[v]) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto [v, w]:d[u]) if (v!=p&&!used[v]&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz);
    return u;
}

void calcdist(int u, int p, ll dist, int dpt)
{
    ds[dpt][u]=dist;
    for (auto [v, w]:d[u]) if (v!=p&&!used[v]) calcdist(v, u, dist+w, dpt);
}

void decomposition(int u, int p, int dpt)
{
    u=findcentroid(u, u, dfssz(u, u));
    used[u]=1;
    c[u]=p;
    lvl[u]=dpt;
    calcdist(u, u, 0, dpt);
    for (auto [v, w]:d[u]) if (v!=p&&!used[v]) decomposition(v, u, dpt+1);
}

void update(int u)
{
    int rt=u;
    while (u!=-1) dp[u]=min(dp[u], ds[lvl[u]][rt]), rem.push_back(u), u=c[u];
}

ll query(int u)
{
    ll tmp=LLONG_MAX, rt=u;
    while (u!=-1) tmp=(dp[u]!=LLONG_MAX)?min(tmp, ds[lvl[u]][rt]+dp[u]):tmp, u=c[u];
    return tmp;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i=0; i<N-1; i++) d[A[i]].push_back({B[i], D[i]}), d[B[i]].push_back({A[i], D[i]});
    for (int i=0; i<N; i++) dp[i]=LLONG_MAX;
    decomposition(0, -1, 1);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll res=LLONG_MAX;
    for (int i=0; i<S; i++) update(X[i]);
    for (int i=0; i<T; i++) res=min(res, query(Y[i]));
    for (auto x:rem) dp[x]=LLONG_MAX;
    rem.clear();
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 53852 KB Output is correct
2 Correct 208 ms 69372 KB Output is correct
3 Correct 227 ms 73356 KB Output is correct
4 Correct 227 ms 73932 KB Output is correct
5 Correct 252 ms 73948 KB Output is correct
6 Correct 150 ms 50772 KB Output is correct
7 Correct 226 ms 71272 KB Output is correct
8 Correct 234 ms 73556 KB Output is correct
9 Correct 246 ms 73808 KB Output is correct
10 Correct 148 ms 50768 KB Output is correct
11 Correct 227 ms 71276 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 53852 KB Output is correct
2 Correct 1210 ms 152536 KB Output is correct
3 Correct 1949 ms 168676 KB Output is correct
4 Correct 419 ms 96788 KB Output is correct
5 Correct 2480 ms 192432 KB Output is correct
6 Correct 1975 ms 169224 KB Output is correct
7 Correct 538 ms 106324 KB Output is correct
8 Correct 220 ms 64448 KB Output is correct
9 Correct 605 ms 109524 KB Output is correct
10 Correct 519 ms 107088 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 53852 KB Output is correct
2 Correct 208 ms 69372 KB Output is correct
3 Correct 227 ms 73356 KB Output is correct
4 Correct 227 ms 73932 KB Output is correct
5 Correct 252 ms 73948 KB Output is correct
6 Correct 150 ms 50772 KB Output is correct
7 Correct 226 ms 71272 KB Output is correct
8 Correct 234 ms 73556 KB Output is correct
9 Correct 246 ms 73808 KB Output is correct
10 Correct 148 ms 50768 KB Output is correct
11 Correct 227 ms 71276 KB Output is correct
12 Correct 8 ms 53852 KB Output is correct
13 Correct 1210 ms 152536 KB Output is correct
14 Correct 1949 ms 168676 KB Output is correct
15 Correct 419 ms 96788 KB Output is correct
16 Correct 2480 ms 192432 KB Output is correct
17 Correct 1975 ms 169224 KB Output is correct
18 Correct 538 ms 106324 KB Output is correct
19 Correct 220 ms 64448 KB Output is correct
20 Correct 605 ms 109524 KB Output is correct
21 Correct 519 ms 107088 KB Output is correct
22 Correct 1562 ms 158628 KB Output is correct
23 Correct 1539 ms 167620 KB Output is correct
24 Correct 2491 ms 179672 KB Output is correct
25 Correct 2459 ms 192952 KB Output is correct
26 Correct 2433 ms 183252 KB Output is correct
27 Correct 3177 ms 210308 KB Output is correct
28 Correct 515 ms 113908 KB Output is correct
29 Correct 2547 ms 182376 KB Output is correct
30 Correct 2363 ms 181856 KB Output is correct
31 Correct 2374 ms 182420 KB Output is correct
32 Correct 695 ms 124724 KB Output is correct
33 Correct 234 ms 73020 KB Output is correct
34 Correct 377 ms 105596 KB Output is correct
35 Correct 388 ms 105556 KB Output is correct
36 Correct 537 ms 112460 KB Output is correct
37 Correct 533 ms 112184 KB Output is correct