oj.uz

Submission #708735

# Submission time Handle Problem Language Result Execution time Memory
708735 2023-03-12T08:52:25 Z Thienu Factories (JOI14_factories) C++17
100 / 100
 6992 ms 220068 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target ("sse4")
//#include "grader.cpp"
#define ll long long
#define pb push_back
#define X first
#define Y second
const int maxmum=500005,maxlift=25;
vector<pair<int,int> > v[maxmum];
int n,lv[maxmum],par[maxmum][maxlift],sz_opt[maxmum];;
ll d[maxmum];
void dfs(int u,int p)
{
    for(int i=0;i<sz_opt[u];i++)
    {
        int node=v[u][i].X,cost=v[u][i].Y;
        if(node==p)continue;
        lv[node]=lv[u]+1;
        d[node]=d[u]+cost;
        par[node][0]=u;
        dfs(node,u);
    }
}
int lca(int a,int b)
{
    if(lv[a]<lv[b])swap(a,b);
    int lv_diff = lv[a] - lv[b];
    for(int i=19;i>=0;i--)
    {
        if(lv_diff & (1 << i))
        {
            a=par[a][i];
        }
    }
    if(a==b)return a;
    for(int i=19;i>=0;i--)
    {
        if(par[a][i]!=par[b][i])
        {
            a=par[a][i],b=par[b][i];
        }
    }
    return par[a][0];
}
ll lca_dis(int a,int b)
{
    return d[a]+d[b]-2*d[lca(a,b)];
}
int sz[maxmum],vis[maxmum],par_cen[maxmum];
ll opt[maxmum][maxlift];
int dfs_sz(int u,int p)
{
    sz[u]=1;
    for(int i=0;i<sz_opt[u];i++)
    {
        int node=v[u][i].X;
        if(node==p||vis[node])continue;
        sz[u]+=dfs_sz(node,u);
    }
    return sz[u];
}
int find_cen(int u,int p,int size)
{
    for(int i=0;i<sz_opt[u];i++)
    {
        int node=v[u][i].X;
        if(node==p||vis[node])continue;
        if(sz[node]>size/2)return find_cen(node,u,size);
    }
    return u;
}
void centroid(int u,int p)
{
    dfs_sz(u,u);
    int cen=find_cen(u,u,sz[u]);
    vis[cen]=1;
    par_cen[cen]=p;
    for(int i=0;i<sz_opt[cen];i++)
    {
        ll node=v[cen][i].X;
        if(node==p||vis[node])continue;
        centroid(node,cen);
    }
}
ll mn[maxmum];
void Init(int N, int A[], int B[], int D[]) 
{
    n=N;
    for(int i=0;i<n-1;i++)
    {
        v[A[i]+1].pb({B[i]+1,D[i]});
        v[B[i]+1].pb({A[i]+1,D[i]});
    }
    for(int i=1;i<=n;i++)sz_opt[i]=v[i].size();
    par[1][0]=1;
    dfs(1,1);
    for(int i=1;i<=19;i++)
    {
        for(int j=1;j<=n;j++)
        {
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }
    dfs_sz(1,1);
    centroid(1,0);
    for(int i=1;i<=n;i++)
    {
        ll x=i,kk=0;
        while(x)
        {
            opt[i][kk]=lca_dis(x,i);
            ++kk;
            x=par_cen[x];
        }
    }
    for(int i=1;i<=n;i++)mn[i]=1e18;
}
void update(int num,int type)
{
    int u=num,kk=0;
    while(u)
    {
        if(type==0)
        {
            mn[u]=min(mn[u],opt[num][kk]);
        }else
        {
            mn[u]=1e18;
        }
        u=par_cen[u];
        ++kk;
    }
}
ll query(ll num)
{
    int u=num,kk=0;
    ll val=1e18;
    while(u)
    {
        val=min(val,opt[num][kk]+mn[u]);
        u=par_cen[u];
        ++kk;
    }
    return val;
}
long long Query(int S, int X[], int T, int Y[]) 
{
    for(int i=0;i<S;i++)
    {
        update(X[i]+1,0);
    }
    ll ans=1e18;
    for(int i=0;i<T;i++)
    {
        ans=min(ans,query(Y[i]+1));
    }
    for(int i=0;i<S;i++)
    {
        update(X[i]+1,1);
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12732 KB Output is correct
2 Correct 304 ms 26036 KB Output is correct
3 Correct 367 ms 25892 KB Output is correct
4 Correct 346 ms 25644 KB Output is correct
5 Correct 373 ms 25748 KB Output is correct
6 Correct 251 ms 26360 KB Output is correct
7 Correct 397 ms 26152 KB Output is correct
8 Correct 334 ms 26020 KB Output is correct
9 Correct 383 ms 25832 KB Output is correct
10 Correct 239 ms 25808 KB Output is correct
11 Correct 322 ms 24500 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12320 KB Output is correct
2 Correct 2456 ms 208124 KB Output is correct
3 Correct 4259 ms 207808 KB Output is correct
4 Correct 719 ms 209428 KB Output is correct
5 Correct 5792 ms 219396 KB Output is correct
6 Correct 4290 ms 209532 KB Output is correct
7 Correct 999 ms 62720 KB Output is correct
8 Correct 393 ms 63732 KB Output is correct
9 Correct 1097 ms 64952 KB Output is correct
10 Correct 1039 ms 64080 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12732 KB Output is correct
2 Correct 304 ms 26036 KB Output is correct
3 Correct 367 ms 25892 KB Output is correct
4 Correct 346 ms 25644 KB Output is correct
5 Correct 373 ms 25748 KB Output is correct
6 Correct 251 ms 26360 KB Output is correct
7 Correct 397 ms 26152 KB Output is correct
8 Correct 334 ms 26020 KB Output is correct
9 Correct 383 ms 25832 KB Output is correct
10 Correct 239 ms 25808 KB Output is correct
11 Correct 322 ms 24500 KB Output is correct
12 Correct 8 ms 12320 KB Output is correct
13 Correct 2456 ms 208124 KB Output is correct
14 Correct 4259 ms 207808 KB Output is correct
15 Correct 719 ms 209428 KB Output is correct
16 Correct 5792 ms 219396 KB Output is correct
17 Correct 4290 ms 209532 KB Output is correct
18 Correct 999 ms 62720 KB Output is correct
19 Correct 393 ms 63732 KB Output is correct
20 Correct 1097 ms 64952 KB Output is correct
21 Correct 1039 ms 64080 KB Output is correct
22 Correct 2844 ms 209880 KB Output is correct
23 Correct 2745 ms 212212 KB Output is correct
24 Correct 5426 ms 210552 KB Output is correct
25 Correct 5197 ms 213624 KB Output is correct
26 Correct 5218 ms 210320 KB Output is correct
27 Correct 6992 ms 220068 KB Output is correct
28 Correct 996 ms 217468 KB Output is correct
29 Correct 4815 ms 214724 KB Output is correct
30 Correct 5376 ms 215128 KB Output is correct
31 Correct 5088 ms 214988 KB Output is correct
32 Correct 1231 ms 76116 KB Output is correct
33 Correct 399 ms 74712 KB Output is correct
34 Correct 744 ms 71304 KB Output is correct
35 Correct 775 ms 71376 KB Output is correct
36 Correct 1049 ms 71528 KB Output is correct
37 Correct 1028 ms 71572 KB Output is correct