oj.uz

Submission #895462

# Submission time Handle Problem Language Result Execution time Memory
895462 2023-12-30T01:39:34 Z 12345678 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 181844 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];
vector<ll> rem;

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)
{
    int rt=u;
    while (u!=-1) dp[u]=min(dp[u], distance(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, 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]);
    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 31 ms 37208 KB Output is correct
2 Correct 1276 ms 42020 KB Output is correct
3 Correct 2122 ms 41692 KB Output is correct
4 Correct 1615 ms 42444 KB Output is correct
5 Correct 2357 ms 42444 KB Output is correct
6 Correct 410 ms 41692 KB Output is correct
7 Correct 2080 ms 41880 KB Output is correct
8 Correct 2110 ms 41960 KB Output is correct
9 Correct 2304 ms 42448 KB Output is correct
10 Correct 410 ms 41868 KB Output is correct
11 Correct 2078 ms 42068 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37208 KB Output is correct
2 Correct 2148 ms 155824 KB Output is correct
3 Correct 5645 ms 159656 KB Output is correct
4 Correct 766 ms 153652 KB Output is correct
5 Execution timed out 8057 ms 181844 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 37208 KB Output is correct
2 Correct 1276 ms 42020 KB Output is correct
3 Correct 2122 ms 41692 KB Output is correct
4 Correct 1615 ms 42444 KB Output is correct
5 Correct 2357 ms 42444 KB Output is correct
6 Correct 410 ms 41692 KB Output is correct
7 Correct 2080 ms 41880 KB Output is correct
8 Correct 2110 ms 41960 KB Output is correct
9 Correct 2304 ms 42448 KB Output is correct
10 Correct 410 ms 41868 KB Output is correct
11 Correct 2078 ms 42068 KB Output is correct
12 Correct 8 ms 37208 KB Output is correct
13 Correct 2148 ms 155824 KB Output is correct
14 Correct 5645 ms 159656 KB Output is correct
15 Correct 766 ms 153652 KB Output is correct
16 Execution timed out 8057 ms 181844 KB Time limit exceeded
17 Halted 0 ms 0 KB -