oj.uz

답안 #708657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708657 2023-03-12T06:51:41 Z ToroTN 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 334916 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 dis[maxmum][maxlift],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;
        dis[node][0]=cost;
        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;
}
int lv_cen[maxmum];
void centroid(int u,int p)
{
    dfs_sz(u,u);
    int cen=find_cen(u,u,sz[u]);
    vis[cen]=1;
    lv_cen[cen]=lv_cen[p]+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++)
        {
            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);
    lv_cen[0]=-1;
    centroid(1,0);
    for(int i=1;i<=n;i++)
    {
        ll x=i;
        while(1)
        {
            opt[i][lv_cen[x]]=lca_dis(x,i);
            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;
    while(1)
    {
        if(type==0)
        {
            mn[u]=min(mn[u],opt[num][lv_cen[u]]);
        }else
        {
            mn[u]=1e18;
        }
        u=par_cen[u];
        if(u==0)break;
    }
}
ll query(ll num)
{
    int u=num;
    ll val=1e18;
    while(1)
    {
        val=min(val,opt[num][lv_cen[u]]+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(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:55: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]
   55 |     for(int i=0;i<v[u].size();i++)
      |                 ~^~~~~~~~~~~~
factories.cpp: In function 'int find_cen(int, int, int)':
factories.cpp:65: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]
   65 |     for(int i=0;i<v[u].size();i++)
      |                 ~^~~~~~~~~~~~
factories.cpp: In function 'void centroid(int, int)':
factories.cpp:81: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]
   81 |     for(int i=0;i<v[cen].size();i++)
      |                 ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12628 KB Output is correct
2 Correct 289 ms 22888 KB Output is correct
3 Correct 303 ms 22948 KB Output is correct
4 Correct 292 ms 23072 KB Output is correct
5 Correct 312 ms 23240 KB Output is correct
6 Correct 211 ms 23016 KB Output is correct
7 Correct 293 ms 23112 KB Output is correct
8 Correct 303 ms 23100 KB Output is correct
9 Correct 328 ms 23248 KB Output is correct
10 Correct 212 ms 22932 KB Output is correct
11 Correct 319 ms 23084 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12500 KB Output is correct
2 Correct 2819 ms 305800 KB Output is correct
3 Correct 6471 ms 308228 KB Output is correct
4 Correct 928 ms 306440 KB Output is correct
5 Execution timed out 8109 ms 334916 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12628 KB Output is correct
2 Correct 289 ms 22888 KB Output is correct
3 Correct 303 ms 22948 KB Output is correct
4 Correct 292 ms 23072 KB Output is correct
5 Correct 312 ms 23240 KB Output is correct
6 Correct 211 ms 23016 KB Output is correct
7 Correct 293 ms 23112 KB Output is correct
8 Correct 303 ms 23100 KB Output is correct
9 Correct 328 ms 23248 KB Output is correct
10 Correct 212 ms 22932 KB Output is correct
11 Correct 319 ms 23084 KB Output is correct
12 Correct 8 ms 12500 KB Output is correct
13 Correct 2819 ms 305800 KB Output is correct
14 Correct 6471 ms 308228 KB Output is correct
15 Correct 928 ms 306440 KB Output is correct
16 Execution timed out 8109 ms 334916 KB Time limit exceeded
17 Halted 0 ms 0 KB -