oj.uz

Submission #895458

# Submission time Handle Problem Language Result Execution time Memory
895458 2023-12-30T01:32:54 Z 12345678 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 200528 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

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

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, w]:d[u]) if (v!=p) ds[v]=ds[u]+w, dfs(v, u);
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return v;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

ll distance(int u, int v)
{
    return ds[u]+ds[v]-2*ds[lca(u, v)];
}

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 decomposition(int u, int p)
{
    u=findcentroid(u, u, dfssz(u, u));
    used[u]=1;
    c[u]=p;
    for (auto [v, w]:d[u]) if (v!=p&&!used[v]) decomposition(v, u);
}

void update(int u, bool remove)
{
    int rt=u;
    while (u!=-1) dp[u]=remove?LLONG_MAX:min(dp[u], distance(u, rt)), u=c[u];
}

ll query(int u)
{
    ll tmp=LLONG_MAX, rt=u;
    while (u!=-1) tmp=(dp[u]!=LLONG_MAX)?min(tmp, distance(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;
    dfs(0, 0);
    decomposition(0, -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], 0);
    for (int i=0; i<T; i++) res=min(res, query(Y[i]));
    for (int i=0; i<S; i++) update(X[i], 1);
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37212 KB Output is correct
2 Correct 1295 ms 51280 KB Output is correct
3 Correct 2139 ms 51312 KB Output is correct
4 Correct 1669 ms 51296 KB Output is correct
5 Correct 2327 ms 51580 KB Output is correct
6 Correct 419 ms 51300 KB Output is correct
7 Correct 2060 ms 51312 KB Output is correct
8 Correct 2149 ms 51304 KB Output is correct
9 Correct 2398 ms 51580 KB Output is correct
10 Correct 425 ms 51148 KB Output is correct
11 Correct 2104 ms 51312 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37432 KB Output is correct
2 Correct 2273 ms 174080 KB Output is correct
3 Correct 6435 ms 177588 KB Output is correct
4 Correct 844 ms 171536 KB Output is correct
5 Execution timed out 8082 ms 200528 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37212 KB Output is correct
2 Correct 1295 ms 51280 KB Output is correct
3 Correct 2139 ms 51312 KB Output is correct
4 Correct 1669 ms 51296 KB Output is correct
5 Correct 2327 ms 51580 KB Output is correct
6 Correct 419 ms 51300 KB Output is correct
7 Correct 2060 ms 51312 KB Output is correct
8 Correct 2149 ms 51304 KB Output is correct
9 Correct 2398 ms 51580 KB Output is correct
10 Correct 425 ms 51148 KB Output is correct
11 Correct 2104 ms 51312 KB Output is correct
12 Correct 9 ms 37432 KB Output is correct
13 Correct 2273 ms 174080 KB Output is correct
14 Correct 6435 ms 177588 KB Output is correct
15 Correct 844 ms 171536 KB Output is correct
16 Execution timed out 8082 ms 200528 KB Time limit exceeded
17 Halted 0 ms 0 KB -