oj.uz

답안 #708647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708647 2023-03-12T06:23:58 Z ToroTN 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 372552 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],d[500005];
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;
        d[node]=d[u]+cost;
        par[node][0]=u;
        dfs(node,u);
    }
}
ll lca(ll a,ll b)
{
    if(lv[a]<lv[b])swap(a,b);
    for(int i=20;i>=0;i--)
    {
        if(lv[par[a][i]]>=lv[b])
        {
            a=par[a][i];
        }
    }
    if(a==b)return a;
    for(int i=20;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(ll a,ll b)
{
    return d[a]+d[b]-2*d[lca(a,b)];
}
ll sz[500005],vis[500005],par_cen[500005],opt[500005][25];
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++)
    {
        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(ll num,ll type)
{
    ll 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)
{
    ll u=num,val=1e18,kk=0;
    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(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:52: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]
   52 |     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:62: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]
   62 |     for(int i=0;i<v[u].size();i++)
      |                 ~^~~~~~~~~~~~
factories.cpp: In function 'void centroid(long long int, long long int)':
factories.cpp:76: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]
   76 |     for(int i=0;i<v[cen].size();i++)
      |                 ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12884 KB Output is correct
2 Correct 266 ms 24096 KB Output is correct
3 Correct 273 ms 24232 KB Output is correct
4 Correct 269 ms 24188 KB Output is correct
5 Correct 285 ms 24448 KB Output is correct
6 Correct 184 ms 24224 KB Output is correct
7 Correct 276 ms 24308 KB Output is correct
8 Correct 273 ms 24252 KB Output is correct
9 Correct 291 ms 24696 KB Output is correct
10 Correct 187 ms 24248 KB Output is correct
11 Correct 281 ms 24208 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12500 KB Output is correct
2 Correct 2830 ms 367708 KB Output is correct
3 Correct 7523 ms 371384 KB Output is correct
4 Correct 933 ms 365248 KB Output is correct
5 Execution timed out 8064 ms 372552 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12884 KB Output is correct
2 Correct 266 ms 24096 KB Output is correct
3 Correct 273 ms 24232 KB Output is correct
4 Correct 269 ms 24188 KB Output is correct
5 Correct 285 ms 24448 KB Output is correct
6 Correct 184 ms 24224 KB Output is correct
7 Correct 276 ms 24308 KB Output is correct
8 Correct 273 ms 24252 KB Output is correct
9 Correct 291 ms 24696 KB Output is correct
10 Correct 187 ms 24248 KB Output is correct
11 Correct 281 ms 24208 KB Output is correct
12 Correct 8 ms 12500 KB Output is correct
13 Correct 2830 ms 367708 KB Output is correct
14 Correct 7523 ms 371384 KB Output is correct
15 Correct 933 ms 365248 KB Output is correct
16 Execution timed out 8064 ms 372552 KB Time limit exceeded
17 Halted 0 ms 0 KB -