oj.uz

Submission #708678

# Submission time Handle Problem Language Result Execution time Memory
708678 2023-03-12T07:11:30 Z ToroTN Factories (JOI14_factories) C++14
15 / 100
 8000 ms 218648 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);
    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++)
    {
        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 14 ms 12500 KB Output is correct
2 Correct 247 ms 21924 KB Output is correct
3 Correct 277 ms 21972 KB Output is correct
4 Correct 276 ms 22016 KB Output is correct
5 Correct 280 ms 22000 KB Output is correct
6 Correct 182 ms 21944 KB Output is correct
7 Correct 266 ms 21952 KB Output is correct
8 Correct 285 ms 21956 KB Output is correct
9 Correct 298 ms 22080 KB Output is correct
10 Correct 199 ms 21916 KB Output is correct
11 Correct 270 ms 21964 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 2523 ms 208060 KB Output is correct
3 Correct 5832 ms 207684 KB Output is correct
4 Correct 764 ms 208580 KB Output is correct
5 Execution timed out 8048 ms 218648 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12500 KB Output is correct
2 Correct 247 ms 21924 KB Output is correct
3 Correct 277 ms 21972 KB Output is correct
4 Correct 276 ms 22016 KB Output is correct
5 Correct 280 ms 22000 KB Output is correct
6 Correct 182 ms 21944 KB Output is correct
7 Correct 266 ms 21952 KB Output is correct
8 Correct 285 ms 21956 KB Output is correct
9 Correct 298 ms 22080 KB Output is correct
10 Correct 199 ms 21916 KB Output is correct
11 Correct 270 ms 21964 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2523 ms 208060 KB Output is correct
14 Correct 5832 ms 207684 KB Output is correct
15 Correct 764 ms 208580 KB Output is correct
16 Execution timed out 8048 ms 218648 KB Time limit exceeded
17 Halted 0 ms 0 KB -