oj.uz

Submission #708641

# Submission time Handle Problem Language Result Execution time Memory
708641 2023-03-12T05:52:05 Z ToroTN Factories (JOI14_factories) C++14
15 / 100
 8000 ms 268408 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
vector<pair<ll,ll> > v[500005];
ll n,lv[500005],dis[500005][25],par[500005][25];
void dfs(ll u,ll p)
{
    for(int i=0;i<v[u].size();i++)
    {
        ll node=v[u][i].X,cost=v[u][i].Y;
        if(node==p)continue;
        lv[node]=lv[u]+1;
        dis[node][0]=cost;
        par[node][0]=u;
        dfs(node,u);
    }
}
pair<ll,ll> lca(ll a,ll b)
{
    ll sum=0;
    if(lv[a]<lv[b])swap(a,b);
    for(int i=20;i>=0;i--)
    {
        if(lv[par[a][i]]>=lv[b])
        {
            sum+=dis[a][i],a=par[a][i];
        }
    }
    if(a==b)return {a,sum};
    for(int i=20;i>=0;i--)
    {
        if(par[a][i]!=par[b][i])
        {
            sum+=dis[a][i],sum+=dis[b][i];
            a=par[a][i],b=par[b][i];
        }
    }
    sum+=dis[a][0],sum+=dis[b][0];
    return {par[a][0],sum};
}
ll sz[500005],vis[500005],par_cen[500005];
ll dfs_sz(ll u,ll p)
{
    sz[u]=1;
    for(int i=0;i<v[u].size();i++)
    {
        ll node=v[u][i].X;
        if(node==p||vis[node])continue;
        sz[u]+=dfs_sz(node,u);
    }
    return sz[u];
}
ll find_cen(ll u,ll p,ll size)
{
    for(int i=0;i<v[u].size();i++)
    {
        ll 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(ll u,ll p)
{
    dfs_sz(u,u);
    ll cen=find_cen(u,u,sz[u]);
    vis[cen]=1;
    par_cen[cen]=p;
    for(int i=0;i<v[cen].size();i++)
    {
        ll node=v[cen][i].X;
        if(node==p||vis[node])continue;
        centroid(node,cen);
    }
}
ll mn[500005];
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]});
    }
    par[1][0]=1;
    dfs(1,1);
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dis[j][i]=dis[j][i-1]+dis[par[j][i-1]][i-1];
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }
    dfs_sz(1,1);
    centroid(1,0);
    for(int i=1;i<=n;i++)mn[i]=1e18;
}
void update(ll num,ll type)
{
    ll u=num;
    while(1)
    {
        if(type==0)
        {
            mn[u]=min(mn[u],lca(u,num).Y);
        }else
        {
            mn[u]=1e18;
        }
        u=par_cen[u];
        if(u==0)break;
    }
}
ll query(ll num)
{
    ll u=num,val=1e18;
    while(1)
    {
        val=min(val,lca(num,u).Y+mn[u]);
        u=par_cen[u];
        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;
}

Compilation message

factories.cpp: In function 'void dfs(long long int, long long int)':
factories.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<v[u].size();i++)
      |                 ~^~~~~~~~~~~~
factories.cpp: In function 'long long int dfs_sz(long long int, long long int)':
factories.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<v[u].size();i++)
      |                 ~^~~~~~~~~~~~
factories.cpp: In function 'long long int find_cen(long long int, long long int, long long int)':
factories.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<v[u].size();i++)
      |                 ~^~~~~~~~~~~~
factories.cpp: In function 'void centroid(long long int, long long int)':
factories.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<v[cen].size();i++)
      |                 ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12756 KB Output is correct
2 Correct 1064 ms 23436 KB Output is correct
3 Correct 1918 ms 23416 KB Output is correct
4 Correct 2013 ms 23452 KB Output is correct
5 Correct 2904 ms 23764 KB Output is correct
6 Correct 347 ms 23580 KB Output is correct
7 Correct 1966 ms 23800 KB Output is correct
8 Correct 2047 ms 23620 KB Output is correct
9 Correct 2552 ms 23856 KB Output is correct
10 Correct 367 ms 23552 KB Output is correct
11 Correct 2031 ms 23684 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12372 KB Output is correct
2 Correct 3556 ms 266008 KB Output is correct
3 Execution timed out 8092 ms 268408 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12756 KB Output is correct
2 Correct 1064 ms 23436 KB Output is correct
3 Correct 1918 ms 23416 KB Output is correct
4 Correct 2013 ms 23452 KB Output is correct
5 Correct 2904 ms 23764 KB Output is correct
6 Correct 347 ms 23580 KB Output is correct
7 Correct 1966 ms 23800 KB Output is correct
8 Correct 2047 ms 23620 KB Output is correct
9 Correct 2552 ms 23856 KB Output is correct
10 Correct 367 ms 23552 KB Output is correct
11 Correct 2031 ms 23684 KB Output is correct
12 Correct 11 ms 12372 KB Output is correct
13 Correct 3556 ms 266008 KB Output is correct
14 Execution timed out 8092 ms 268408 KB Time limit exceeded
15 Halted 0 ms 0 KB -