oj.uz

답안 #708742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708742 2023-03-12T08:56:16 Z Thienu 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 218560 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target ("sse4")
//#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],sz_opt[maxmum];;
ll d[maxmum];
void dfs(int u,int p)
{
    for(int i=0;i<sz_opt[u];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<sz_opt[u];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<sz_opt[u];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<sz_opt[cen];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]});
    }
    for(int i=1;i<=n;i++)sz_opt[i]=v[i].size();
    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(x)
        {
            opt[i][kk]=lca_dis(x,i);
            ++kk;
            x=par_cen[x];
        }
    }
    for(int i=1;i<=n;i++)mn[i]=1e18;
}
void update(int num,int type)
{
    int u=num,kk=0;
    while(u)
    {
        if(type==0)
        {
            mn[u]=min(mn[u],opt[num][kk]);
        }else
        {
            mn[u]=1e18;
        }
        u=par_cen[u];
        ++kk;
    }
}
ll query(ll num)
{
    int u=num,kk=0;
    ll val=1e18;
    while(u)
    {
        val=min(val,opt[num][kk]+mn[u]);
        u=par_cen[u];
        ++kk;
    }
    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;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12500 KB Output is correct
2 Correct 252 ms 22200 KB Output is correct
3 Correct 294 ms 22200 KB Output is correct
4 Correct 285 ms 22188 KB Output is correct
5 Correct 301 ms 22336 KB Output is correct
6 Correct 193 ms 22056 KB Output is correct
7 Correct 267 ms 22136 KB Output is correct
8 Correct 285 ms 22092 KB Output is correct
9 Correct 294 ms 22044 KB Output is correct
10 Correct 183 ms 21932 KB Output is correct
11 Correct 304 ms 22076 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 2549 ms 207900 KB Output is correct
3 Correct 6060 ms 207756 KB Output is correct
4 Correct 788 ms 208604 KB Output is correct
5 Execution timed out 8093 ms 218560 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12500 KB Output is correct
2 Correct 252 ms 22200 KB Output is correct
3 Correct 294 ms 22200 KB Output is correct
4 Correct 285 ms 22188 KB Output is correct
5 Correct 301 ms 22336 KB Output is correct
6 Correct 193 ms 22056 KB Output is correct
7 Correct 267 ms 22136 KB Output is correct
8 Correct 285 ms 22092 KB Output is correct
9 Correct 294 ms 22044 KB Output is correct
10 Correct 183 ms 21932 KB Output is correct
11 Correct 304 ms 22076 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 2549 ms 207900 KB Output is correct
14 Correct 6060 ms 207756 KB Output is correct
15 Correct 788 ms 208604 KB Output is correct
16 Execution timed out 8093 ms 218560 KB Time limit exceeded
17 Halted 0 ms 0 KB -