oj.uz

답안 #708649

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708649 2023-03-12T06:30:07 Z ToroTN 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 392924 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=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(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<=19;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 13 ms 12756 KB Output is correct
2 Correct 246 ms 23900 KB Output is correct
3 Correct 286 ms 23880 KB Output is correct
4 Correct 267 ms 23884 KB Output is correct
5 Correct 291 ms 24308 KB Output is correct
6 Correct 206 ms 24016 KB Output is correct
7 Correct 280 ms 23952 KB Output is correct
8 Correct 283 ms 24028 KB Output is correct
9 Correct 283 ms 24540 KB Output is correct
10 Correct 184 ms 24012 KB Output is correct
11 Correct 271 ms 23968 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12576 KB Output is correct
2 Correct 2738 ms 367496 KB Output is correct
3 Correct 7376 ms 371340 KB Output is correct
4 Correct 947 ms 365308 KB Output is correct
5 Execution timed out 8084 ms 392924 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12756 KB Output is correct
2 Correct 246 ms 23900 KB Output is correct
3 Correct 286 ms 23880 KB Output is correct
4 Correct 267 ms 23884 KB Output is correct
5 Correct 291 ms 24308 KB Output is correct
6 Correct 206 ms 24016 KB Output is correct
7 Correct 280 ms 23952 KB Output is correct
8 Correct 283 ms 24028 KB Output is correct
9 Correct 283 ms 24540 KB Output is correct
10 Correct 184 ms 24012 KB Output is correct
11 Correct 271 ms 23968 KB Output is correct
12 Correct 8 ms 12576 KB Output is correct
13 Correct 2738 ms 367496 KB Output is correct
14 Correct 7376 ms 371340 KB Output is correct
15 Correct 947 ms 365308 KB Output is correct
16 Execution timed out 8084 ms 392924 KB Time limit exceeded
17 Halted 0 ms 0 KB -