oj.uz

Submission #708665

# Submission time Handle Problem Language Result Execution time Memory
708665 2023-03-12T06:57:32 Z ToroTN Factories (JOI14_factories) C++14
33 / 100
 8000 ms 236768 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];
ll d[maxmum];
void dfs(int u,int p)
{
    for(int i=0;i<v[u].size();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<v[u].size();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<v[u].size();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<v[cen].size();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]});
    }
    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;
}

Compilation message

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

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 21896 KB Output is correct
3 Correct 263 ms 21956 KB Output is correct
4 Correct 276 ms 21936 KB Output is correct
5 Correct 304 ms 22260 KB Output is correct
6 Correct 185 ms 21884 KB Output is correct
7 Correct 281 ms 21960 KB Output is correct
8 Correct 273 ms 21992 KB Output is correct
9 Correct 282 ms 22232 KB Output is correct
10 Correct 214 ms 21932 KB Output is correct
11 Correct 292 ms 21996 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12372 KB Output is correct
2 Correct 2575 ms 205864 KB Output is correct
3 Correct 6446 ms 208296 KB Output is correct
4 Correct 832 ms 206608 KB Output is correct
5 Correct 7551 ms 236768 KB Output is correct
6 Correct 5986 ms 209884 KB Output is correct
7 Correct 1124 ms 63652 KB Output is correct
8 Correct 367 ms 63996 KB Output is correct
9 Correct 1336 ms 67772 KB Output is correct
10 Correct 1054 ms 64732 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12500 KB Output is correct
2 Correct 247 ms 21896 KB Output is correct
3 Correct 263 ms 21956 KB Output is correct
4 Correct 276 ms 21936 KB Output is correct
5 Correct 304 ms 22260 KB Output is correct
6 Correct 185 ms 21884 KB Output is correct
7 Correct 281 ms 21960 KB Output is correct
8 Correct 273 ms 21992 KB Output is correct
9 Correct 282 ms 22232 KB Output is correct
10 Correct 214 ms 21932 KB Output is correct
11 Correct 292 ms 21996 KB Output is correct
12 Correct 10 ms 12372 KB Output is correct
13 Correct 2575 ms 205864 KB Output is correct
14 Correct 6446 ms 208296 KB Output is correct
15 Correct 832 ms 206608 KB Output is correct
16 Correct 7551 ms 236768 KB Output is correct
17 Correct 5986 ms 209884 KB Output is correct
18 Correct 1124 ms 63652 KB Output is correct
19 Correct 367 ms 63996 KB Output is correct
20 Correct 1336 ms 67772 KB Output is correct
21 Correct 1054 ms 64732 KB Output is correct
22 Correct 2726 ms 207892 KB Output is correct
23 Correct 2674 ms 210244 KB Output is correct
24 Correct 5924 ms 210560 KB Output is correct
25 Correct 6288 ms 214028 KB Output is correct
26 Correct 6250 ms 210672 KB Output is correct
27 Execution timed out 8055 ms 231624 KB Time limit exceeded
28 Halted 0 ms 0 KB -