oj.uz

Submission #941381

# Submission time Handle Problem Language Result Execution time Memory
941381 2024-03-08T16:22:58 Z cpptowin Factories (JOI14_factories) C++17
0 / 100
 18 ms 68256 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 = 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]));
    fo(i,0,S - 1) del(X[i]);
    return res;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 68184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 68256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 68184 KB Output isn't correct
2 Halted 0 ms 0 KB -