제출 #941363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
941363		cpptowin	공장들 (JOI14_factories)	C++17	0 / 100	86 ms	138004 KiB

factories

#include"factories.h"
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define fi first
#define se second
#define pb emplace_back
#define inf 1000000000000000
#define pii pair<int,int>
#define vii vector<pii>
#define vi vector<int>
using namespace std;
long long n,q;
vector<pair<long long,long long>> ke[maxn];
long long minn[maxn];
bool is_remove[maxn];
long long sz[maxn];
vector<pair<long long,long long>> par[maxn];
long long x[maxn],y[maxn];
long long dfs_size(long long u,long long parent = -1)
{
    sz[u] = 1;
    for(auto [v,_] : ke[u])
    {
        if(v == parent or is_remove[v]) continue;
        sz[u] += dfs_size(v,u);
    }
    return sz[u];
}
long long dfs_centroid(long long u,long long tree_size,long long parent = 0)
{
    for(auto [v,_] : ke[u])
    {
        if(v == parent or is_remove[v]) continue;
        if(2 * sz[v] > tree_size) return dfs_centroid(v,tree_size,u);
    }
    return u;
}
void dfs_dist(long long u,long long parent,long long centroid,long long cur_len)
{
    for(auto [v,w] : ke[u])
    {
        if(v == parent or is_remove[v]) continue;
        dfs_dist(v,u,centroid,cur_len + w);
    }
    par[u].pb(cur_len,centroid);
}
void build_centroid(long long u)
{
    long long centroid = dfs_centroid(u,dfs_size(u));
    is_remove[centroid] = 1;
    // do sth
    for(auto [v,w] : ke[centroid])
    {
        if(is_remove[v]) continue;
        dfs_dist(v,centroid,centroid,w);
    }
    for(auto [v,w] : ke[centroid])
    {
        if(is_remove[v]) continue;
        build_centroid(v);
    }
}
void update(long long u)
{
    minn[u] = 0;
    for(auto [dist,centroid] : par[u])
    {
        minn[centroid] = min(minn[centroid],dist);
    }
}
void del(long long u)
{
    minn[u] = inf;
    for(auto [_,centroid] : par[u])
    {
        minn[centroid] = inf;
    }
}
long long get(long long u)
{
    long long ans = minn[u];
    for(auto [dist,centroid] : par[u])
    {
        ans = min(ans,dist + minn[centroid]);
    }
    return ans;
}
void Init(int N, int A[], int B[], int D[])
{
    fo(i,0,N - 2)
    {
        ke[A[i]].pb(B[i],D[i]);
        ke[B[i]].pb(A[i],D[i]);
    }
    build_centroid(0);
}
long long Query(int S, int X[], int T, int Y[])
{
    fo(i,0,S - 1) update(X[i]);
    long long res = 1e18;
    fo(i,0,T - 1) res = min(res,get(Y[i]));
    cout << res << "\n";
    fo(i,0,S - 1) del(X[i]);
}
//main()
//{
//    #define name "TASK"
//    if(fopen(name".inp","r"))
//    {
//       freopen(name".inp","r",stdin);
//       freopen(name".out","w",stdout);
//    }
//    ios_base::sync_with_stdio(false);cin.tie(NULL);
//    cin >> n >> q;
//    fo(i,0,n - 1) minn[i] = inf;
//    fo(i,1,n - 1)
//    {
//        int u,v,w;
//        cin >> u >> v >> w;
//        ke[u].pb(v,w);
//        ke[v].pb(u,w);
//    }
//    build_centroid(0);
//    while(q--)
//    {
//        int s,t;
//        cin >> s >> t;
//        fo(i,1,s)
//        {
//            cin >> x[i];
//            update(x[i]);
//        }
//        int res = inf;
//        fo(i,1,t)
//        {
//            cin >> y[i];
//            res = min(res,get(y[i]));
//        }
//        cout << res;en;
//        fo(i,1,s) del(x[i]);
//    }
//}

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:106:1: warning: no return statement in function returning non-void [-Wreturn-type]
  106 | }
      | ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67