oj.uz

Submission #941378

# Submission time Handle Problem Language Result Execution time Memory
941378 2024-03-08T16:21:31 Z cpptowin Factories (JOI14_factories) C++17
0 / 100
 103 ms 137980 KB 
#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 = -1)
{
    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] + 1].pb(B[i] + 1,D[i]);
        ke[B[i] + 1].pb(A[i] + 1,D[i]);
    }
    build_centroid(1);
}
long long Query(int S, int X[], int T, int Y[])
{
    fo(i,0,S - 1) update(X[i] + 1);
    long long res = 1e18;
    fo(i,0,T - 1) res = min(res,get(Y[i] + 1));
    cout << res << "\n";
    fo(i,0,S - 1) del(X[i] + 1);
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 137948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 137980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 137948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -