oj.uz

Submission #708742

# Submission time Handle Problem Language Result Execution time Memory
708742 2023-03-12T08:56:16 Z Thienu Factories (JOI14_factories) C++17
15 / 100
 8000 ms 218560 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(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 12 ms 12500 KB Output is correct
2 Correct 252 ms 22200 KB Output is correct
3 Correct 294 ms 22200 KB Output is correct
4 Correct 285 ms 22188 KB Output is correct
5 Correct 301 ms 22336 KB Output is correct
6 Correct 193 ms 22056 KB Output is correct
7 Correct 267 ms 22136 KB Output is correct
8 Correct 285 ms 22092 KB Output is correct
9 Correct 294 ms 22044 KB Output is correct
10 Correct 183 ms 21932 KB Output is correct
11 Correct 304 ms 22076 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 2549 ms 207900 KB Output is correct
3 Correct 6060 ms 207756 KB Output is correct
4 Correct 788 ms 208604 KB Output is correct
5 Execution timed out 8093 ms 218560 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12500 KB Output is correct
2 Correct 252 ms 22200 KB Output is correct
3 Correct 294 ms 22200 KB Output is correct
4 Correct 285 ms 22188 KB Output is correct
5 Correct 301 ms 22336 KB Output is correct
6 Correct 193 ms 22056 KB Output is correct
7 Correct 267 ms 22136 KB Output is correct
8 Correct 285 ms 22092 KB Output is correct
9 Correct 294 ms 22044 KB Output is correct
10 Correct 183 ms 21932 KB Output is correct
11 Correct 304 ms 22076 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2549 ms 207900 KB Output is correct
14 Correct 6060 ms 207756 KB Output is correct
15 Correct 788 ms 208604 KB Output is correct
16 Execution timed out 8093 ms 218560 KB Time limit exceeded
17 Halted 0 ms 0 KB -