oj.uz

Submission #708673

# Submission time Handle Problem Language Result Execution time Memory
708673 2023-03-12T07:03:21 Z ToroTN Factories (JOI14_factories) C++14
33 / 100
 8000 ms 238788 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++)
    {
        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 12464 KB Output is correct
2 Correct 255 ms 22896 KB Output is correct
3 Correct 279 ms 22904 KB Output is correct
4 Correct 289 ms 22912 KB Output is correct
5 Correct 300 ms 23244 KB Output is correct
6 Correct 195 ms 23700 KB Output is correct
7 Correct 295 ms 23640 KB Output is correct
8 Correct 289 ms 23744 KB Output is correct
9 Correct 292 ms 24084 KB Output is correct
10 Correct 190 ms 23644 KB Output is correct
11 Correct 275 ms 23736 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 2505 ms 207828 KB Output is correct
3 Correct 5599 ms 210364 KB Output is correct
4 Correct 761 ms 208692 KB Output is correct
5 Correct 7540 ms 238788 KB Output is correct
6 Correct 5947 ms 211840 KB Output is correct
7 Correct 1012 ms 60564 KB Output is correct
8 Correct 342 ms 60992 KB Output is correct
9 Correct 1306 ms 64684 KB Output is correct
10 Correct 1047 ms 61836 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12464 KB Output is correct
2 Correct 255 ms 22896 KB Output is correct
3 Correct 279 ms 22904 KB Output is correct
4 Correct 289 ms 22912 KB Output is correct
5 Correct 300 ms 23244 KB Output is correct
6 Correct 195 ms 23700 KB Output is correct
7 Correct 295 ms 23640 KB Output is correct
8 Correct 289 ms 23744 KB Output is correct
9 Correct 292 ms 24084 KB Output is correct
10 Correct 190 ms 23644 KB Output is correct
11 Correct 275 ms 23736 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2505 ms 207828 KB Output is correct
14 Correct 5599 ms 210364 KB Output is correct
15 Correct 761 ms 208692 KB Output is correct
16 Correct 7540 ms 238788 KB Output is correct
17 Correct 5947 ms 211840 KB Output is correct
18 Correct 1012 ms 60564 KB Output is correct
19 Correct 342 ms 60992 KB Output is correct
20 Correct 1306 ms 64684 KB Output is correct
21 Correct 1047 ms 61836 KB Output is correct
22 Correct 2604 ms 209912 KB Output is correct
23 Correct 2711 ms 212292 KB Output is correct
24 Correct 6264 ms 212652 KB Output is correct
25 Correct 6133 ms 216060 KB Output is correct
26 Correct 6136 ms 212868 KB Output is correct
27 Execution timed out 8098 ms 233580 KB Time limit exceeded
28 Halted 0 ms 0 KB -