oj.uz

Submission #708714

# Submission time Handle Problem Language Result Execution time Memory
708714 2023-03-12T08:28:23 Z ToroTN Factories (JOI14_factories) C++14
15 / 100
 8000 ms 237580 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
//#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);
    for(int i=19;i>=0;i--)
    {
        if(lv[par[a][i]]>=lv[b])
        {
            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(1)
        {
            opt[i][kk]=lca_dis(x,i);
            ++kk;
            x=par_cen[x];
            if(x==0)break;
        }
    }
    for(int i=1;i<=n;i++)mn[i]=1e18;
}
void update(int num,int type)
{
    int u=num,kk=0;
    while(1)
    {
        if(type==0)
        {
            mn[u]=min(mn[u],opt[num][kk]);
        }else
        {
            mn[u]=1e18;
        }
        u=par_cen[u];
        ++kk;
        if(u==0)break;
    }
}
ll query(ll num)
{
    int u=num,kk=0;
    ll val=1e18;
    while(1)
    {
        val=min(val,opt[num][kk]+mn[u]);
        u=par_cen[u];
        ++kk;
        if(u==0)break;
    }
    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++)
    {
        int u=Y[i]+1,kk=0;
        while(1)
        {
            ans=min(ans,opt[Y[i]+1][kk]+mn[u]);
            u=par_cen[u];
            ++kk;
            if(u==0)break;
        }
    }
    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 13 ms 12628 KB Output is correct
2 Correct 271 ms 22948 KB Output is correct
3 Correct 306 ms 22860 KB Output is correct
4 Correct 290 ms 22740 KB Output is correct
5 Correct 294 ms 23012 KB Output is correct
6 Correct 238 ms 22764 KB Output is correct
7 Correct 310 ms 22860 KB Output is correct
8 Correct 297 ms 22836 KB Output is correct
9 Correct 322 ms 23052 KB Output is correct
10 Correct 217 ms 22908 KB Output is correct
11 Correct 310 ms 22640 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 2417 ms 208128 KB Output is correct
3 Correct 6107 ms 210568 KB Output is correct
4 Correct 806 ms 209156 KB Output is correct
5 Execution timed out 8092 ms 237580 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12628 KB Output is correct
2 Correct 271 ms 22948 KB Output is correct
3 Correct 306 ms 22860 KB Output is correct
4 Correct 290 ms 22740 KB Output is correct
5 Correct 294 ms 23012 KB Output is correct
6 Correct 238 ms 22764 KB Output is correct
7 Correct 310 ms 22860 KB Output is correct
8 Correct 297 ms 22836 KB Output is correct
9 Correct 322 ms 23052 KB Output is correct
10 Correct 217 ms 22908 KB Output is correct
11 Correct 310 ms 22640 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2417 ms 208128 KB Output is correct
14 Correct 6107 ms 210568 KB Output is correct
15 Correct 806 ms 209156 KB Output is correct
16 Execution timed out 8092 ms 237580 KB Time limit exceeded
17 Halted 0 ms 0 KB -