oj.uz

Submission #708718

# Submission time Handle Problem Language Result Execution time Memory
708718 2023-03-12T08:33:00 Z ToroTN Factories (JOI14_factories) C++14
15 / 100
 8000 ms 237340 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;
    }
}
long long Query(int S, int X[], int T, int Y[]) 
{
    for(int i=0;i<S;i++)
    {
        int u=X[i]+1,kk=0;
        while(1)
        {
            mn[u]=min(mn[u],opt[X[i]+1][kk]);
            u=par_cen[u];
            ++kk;
            if(u==0)break;
        }
    }
    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++)
    {
        int u=X[i]+1,kk=0;
        while(1)
        {
            mn[u]=1e18;
            u=par_cen[u];
            ++kk;
            if(u==0)break;
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12500 KB Output is correct
2 Correct 281 ms 21900 KB Output is correct
3 Correct 335 ms 21960 KB Output is correct
4 Correct 284 ms 21964 KB Output is correct
5 Correct 286 ms 22336 KB Output is correct
6 Correct 311 ms 21972 KB Output is correct
7 Correct 317 ms 21944 KB Output is correct
8 Correct 298 ms 22100 KB Output is correct
9 Correct 354 ms 22240 KB Output is correct
10 Correct 225 ms 21984 KB Output is correct
11 Correct 302 ms 21976 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12372 KB Output is correct
2 Correct 2479 ms 207896 KB Output is correct
3 Correct 5554 ms 210288 KB Output is correct
4 Correct 767 ms 208608 KB Output is correct
5 Execution timed out 8034 ms 237340 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 12500 KB Output is correct
2 Correct 281 ms 21900 KB Output is correct
3 Correct 335 ms 21960 KB Output is correct
4 Correct 284 ms 21964 KB Output is correct
5 Correct 286 ms 22336 KB Output is correct
6 Correct 311 ms 21972 KB Output is correct
7 Correct 317 ms 21944 KB Output is correct
8 Correct 298 ms 22100 KB Output is correct
9 Correct 354 ms 22240 KB Output is correct
10 Correct 225 ms 21984 KB Output is correct
11 Correct 302 ms 21976 KB Output is correct
12 Correct 10 ms 12372 KB Output is correct
13 Correct 2479 ms 207896 KB Output is correct
14 Correct 5554 ms 210288 KB Output is correct
15 Correct 767 ms 208608 KB Output is correct
16 Execution timed out 8034 ms 237340 KB Time limit exceeded
17 Halted 0 ms 0 KB -