oj.uz

Submission #895467

# Submission time Handle Problem Language Result Execution time Memory
895467 2023-12-30T01:47:44 Z 12345678 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 192188 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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);
    //for (int i=0; i<N; i++) cout<<i<<' '<<c[i]<<'\n';
}

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 17 ms 39256 KB Output is correct
2 Correct 553 ms 44012 KB Output is correct
3 Correct 1219 ms 43888 KB Output is correct
4 Correct 992 ms 44368 KB Output is correct
5 Correct 1600 ms 44624 KB Output is correct
6 Correct 221 ms 43872 KB Output is correct
7 Correct 1246 ms 43996 KB Output is correct
8 Correct 1300 ms 43972 KB Output is correct
9 Correct 1614 ms 44492 KB Output is correct
10 Correct 220 ms 43852 KB Output is correct
11 Correct 1251 ms 43892 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 39256 KB Output is correct
2 Correct 1705 ms 155468 KB Output is correct
3 Correct 4864 ms 160628 KB Output is correct
4 Correct 655 ms 153400 KB Output is correct
5 Correct 7615 ms 189880 KB Output is correct
6 Correct 5182 ms 179188 KB Output is correct
7 Correct 3043 ms 87496 KB Output is correct
8 Correct 372 ms 86472 KB Output is correct
9 Correct 4607 ms 91300 KB Output is correct
10 Correct 3403 ms 88052 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39256 KB Output is correct
2 Correct 553 ms 44012 KB Output is correct
3 Correct 1219 ms 43888 KB Output is correct
4 Correct 992 ms 44368 KB Output is correct
5 Correct 1600 ms 44624 KB Output is correct
6 Correct 221 ms 43872 KB Output is correct
7 Correct 1246 ms 43996 KB Output is correct
8 Correct 1300 ms 43972 KB Output is correct
9 Correct 1614 ms 44492 KB Output is correct
10 Correct 220 ms 43852 KB Output is correct
11 Correct 1251 ms 43892 KB Output is correct
12 Correct 7 ms 39256 KB Output is correct
13 Correct 1705 ms 155468 KB Output is correct
14 Correct 4864 ms 160628 KB Output is correct
15 Correct 655 ms 153400 KB Output is correct
16 Correct 7615 ms 189880 KB Output is correct
17 Correct 5182 ms 179188 KB Output is correct
18 Correct 3043 ms 87496 KB Output is correct
19 Correct 372 ms 86472 KB Output is correct
20 Correct 4607 ms 91300 KB Output is correct
21 Correct 3403 ms 88052 KB Output is correct
22 Correct 3043 ms 183404 KB Output is correct
23 Correct 2525 ms 188016 KB Output is correct
24 Execution timed out 8095 ms 192188 KB Time limit exceeded
25 Halted 0 ms 0 KB -